<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,user-scalable=no"><title>数据的排序 | InsectMk的个人空间</title><meta name="keywords" content="Java,千锋教育,培训"><meta name="author" content="InsectMk,3067836615@qq.com"><meta name="copyright" content="InsectMk"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#f7f9fe"><meta name="mobile-web-app-capable" content="yes"><meta name="apple-touch-fullscreen" content="yes"><meta name="apple-mobile-web-app-title" content="数据的排序"><meta name="application-name" content="数据的排序"><meta name="apple-mobile-web-app-capable" content="yes"><meta name="apple-mobile-web-app-status-bar-style" content="#f7f9fe"><meta property="og:type" content="article"><meta property="og:title" content="数据的排序"><meta property="og:url" content="https://insectmk.top/posts/1a656c15/index.html"><meta property="og:site_name" content="InsectMk的个人空间"><meta property="og:description" content="数组的排序前言排序概念 排序是将一组数据，依据指定的顺序进行排列的过程。 排序是算法中的一部分，也叫排序算法。算法处理数据，而数据的处理最好是要找到他们的规律，这个规律中有很大一部分就是要进行排序，所以需要有排序算法。  常见的排序算法分类 排序分为：内部排序和外部排序。  内部排序：是将需要处理的"><meta property="og:locale" content="zh-CN"><meta property="og:image" content="https://insectmk.top/static/img/head/insectmk.jpg"><meta property="article:author" content="InsectMk"><meta property="article:tag" content="[&quot;InsectMk&quot;,&quot;个人博客&quot;]"><meta name="twitter:card" content="summary"><meta name="twitter:image" content="https://insectmk.top/static/img/head/insectmk.jpg"><meta name="description" content="数组的排序前言排序概念 排序是将一组数据，依据指定的顺序进行排列的过程。 排序是算法中的一部分，也叫排序算法。算法处理数据，而数据的处理最好是要找到他们的规律，这个规律中有很大一部分就是要进行排序，所以需要有排序算法。  常见的排序算法分类 排序分为：内部排序和外部排序。  内部排序：是将需要处理的"><link rel="shortcut icon" href="/static/img/website/favicon.jpg"><link rel="canonical" href="https://insectmk.top/posts/1a656c15/"><link rel="preconnect" href="//cdn.cbd.int"><link rel="preconnect" href="//busuanzi.ibruce.info"><meta name="google-site-verification" content="xxx"><meta name="baidu-site-verification" content="code-xxx"><meta name="msvalidate.01" content="xxx"><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.cbd.int/node-snackbar@0.1.16/dist/snackbar.min.css" media="print" onload='this.media="all"'><link rel="stylesheet" href="https://cdn.cbd.int/@fancyapps/ui@5.0.28/dist/fancybox/fancybox.css" media="print" onload='this.media="all"'><script>let GLOBAL_CONFIG={linkPageTop:{enable:!0,title:"与数百名博主无限进步",addFriendPlaceholder:"昵称（请勿包含博客等字样）：\n网站地址（要求博客地址，请勿提交个人主页）：\n头像图片url（请提供尽可能清晰的图片，我会上传到我自己的图床）：\n描述：\n站点截图（可选）：\n"},peoplecanvas:{enable:!0,img:"https://image.insectmk.cn/hexo-gitee-blog/article/_post/summary/hello-world/cover.jpg"},postHeadAiDescription:void 0,diytitle:void 0,LA51:void 0,greetingBox:void 0,twikooEnvId:"",commentBarrageConfig:void 0,root:"/",preloader:{source:3},friends_vue_info:void 0,navMusic:!0,mainTone:void 0,authorStatus:void 0,algolia:void 0,localSearch:{path:"/search.xml",preload:!0,languages:{hits_empty:"找不到您查询的内容：${query}"}},translate:{defaultEncoding:2,translateDelay:0,msgToTraditionalChinese:"繁",msgToSimplifiedChinese:"简",rightMenuMsgToTraditionalChinese:"转为繁体",rightMenuMsgToSimplifiedChinese:"转为简体"},noticeOutdate:void 0,highlight:{plugin:"highlight.js",highlightCopy:!0,highlightLang:!0,highlightHeightLimit:330},copy:{success:"复制成功",error:"复制错误",noSupport:"浏览器不支持"},relativeDate:{homepage:!1,simplehomepage:!0,post:!1},runtime:"天",date_suffix:{just:"刚刚",min:"分钟前",hour:"小时前",day:"天前",month:"个月前"},copyright:{copy:!0,copyrightEbable:!1,limitCount:50,languages:{author:"作者: InsectMk",link:"链接: ",source:"来源: InsectMk的个人空间",info:"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。",copySuccess:"复制成功，复制和转载请标注本文地址"}},lightbox:"fancybox",Snackbar:{chs_to_cht:"你已切换为繁体",cht_to_chs:"你已切换为简体",day_to_night:"你已切换为深色模式",night_to_day:"你已切换为浅色模式",bgLight:"#425AEF",bgDark:"#1f1f1f",position:"top-center"},source:{justifiedGallery:{js:"https://cdn.cbd.int/flickr-justified-gallery@2.1.2/dist/fjGallery.min.js",css:"https://cdn.cbd.int/flickr-justified-gallery@2.1.2/dist/fjGallery.css"}},isPhotoFigcaption:!1,islazyload:!1,isAnchor:!1,shortcutKey:void 0,autoDarkmode:!0}</script><script id="config-diff">var GLOBAL_CONFIG_SITE={configTitle:"InsectMk的个人空间",title:"数据的排序",postAI:"",pageFillDescription:"数组的排序, 前言, 排序概念, 常见的排序算法分类, 算法稳定性, 如何分析算法, 分析算法的执行效率, 分析排序算法的稳定性, 分析排序算法的内存损耗, 冒泡排序, 概念, 原理, 代码实现, 口诀, 优化代码, 选择排序, 概念, 原理, 代码实现, 选择排序小结, 插入排序, 概念, 原理, 代码实现, 插入排序小结, 快速排序, 概念, 原理, 步骤, A.双边循环法, 代码实现, B.单边循环法, 代码实现, 希尔排序, 概念, 原理, 代码实现, 希尔排序优劣, 希尔排序稳定性, 归并排序, 概念, 原理, 代码实现, 桶排序, 概念, 原理, 代码实现, 基数排序, 概念, 原理, 代码实现, 计数排序, 概念, 原理, 代码实现, 堆排序, 概念, 原理, 代码实现, Arrays.sort(), 概念, 原理, 源码截图, 排序算法与复杂度归类数组的排序前言排序概念排序是将一组数据依据指定的顺序进行排列的过程排序是算法中的一部分也叫排序算法算法处理数据而数据的处理最好是要找到他们的规律这个规律中有很大一部分就是要进行排序所以需要有排序算法常见的排序算法分类排序分为内部排序和外部排序内部排序是将需要处理的所有数据加载到内存中进行排序外部排序当数据量过大无法全部加载到内存中需要借助外部存储文件磁盘等进行排序交换排序冒泡排序快速排序选择排序选择排序堆排序插入排序插入排序希尔排序归并排序桶排序计数排序基数排序算法稳定性假设在数列中存在若在排序之前在前面并且排序之后仍然在前面则这个排序算法是稳定的如何分析算法分析算法的执行效率最好最坏平均情况时间复杂度时间复杂度的系数常数和低阶比较次数交换或移动次数分析排序算法的稳定性概念如果待排序的序列中存在值相等的元素经过排序之后相等元素之间原有的先后顺序不变稳定性重要性可针对对象的多种属性进行有优先级的排序举例给电商交易系统中的订单排序按照金额大小对订单数据排序对于相同金额的订单以下单时间早晚排序用稳定排序算法可简洁地解决先按照下单时间给订单排序排序完成后用稳定排序算法按照订单金额重新排序分析排序算法的内存损耗原地排序算法特指空间复杂度是的排序算法冒泡排序概念冒泡排序是最基础的排序算法属于交换排序算法冒泡排序重复地遍历要排序的数组元素一次比较两个元素如果他们的顺序错误就把他们交换过来重复地进行直到没有再需要交换也就是说该数组已经排序完成这个算法的名字由来是因为越大的元素会经过交换慢慢浮到数列的顶端故名冒泡排序按照冒泡排序的思想把相邻的元素两两比较当一个元素大于右侧相邻元素时交换它们的位置当一个元素小于或等于右侧相邻元素时位置不变冒泡排序只会操作相邻的两个数据每次冒泡操作都会对相邻的两个元素进行比较看是否满足大小关系要求如果不满足就让它俩互换原理比较相邻的元素如果第一个比第二个大就交换他们两个对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对在这一点最后的元素应该会是最大的数针对所有的元素重复以上的步骤除了最后一个持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较经过第一轮后元素作为数列中最大的元素就像是汽水里的小气泡一样漂到了最右侧每一轮结束都会有一个元素被移到最右侧代码实现通过第三方变量实现两个变量的交换缺点需要声明变量通过两个变量加减实现两个变量的交换缺点当两个变量相加超出取值范围会损失精度通过位运算异或实现两个变量的交换口诀个数字来排队两两相比小靠前外层循环内层循环优化代码为什么需要优化针对不同的数列需要循环的轮数是有不同的例如需要轮循环之后才能排好序而当执行第一轮循环后所有相邻的两个数值都无需换位那说明排序正常无需排序不用执行后续的循环默认排好了排好了跳出循环选择排序概念选择排序将数组分成已排序区间和未排序区间初始已排序区间为空每次从未排序区间中选出最小的元素放到已排序区间的末尾直到未排序区间为空原理选择排序是一种最简单的排序算法其排序的逻辑如下有一个待排序的数组从中找出最小的元素将找到的最小元素跟数组中第一个元素交换位置如果最小元素就是第一个元素则自己跟自己交换位置如下图如上图长方形高低代表数字的大小找到最小的数字跟第一个位置的数据进行交换交换之后结果如下图所示然后在剩下的个数字中再找到最小的那个数字跟第个位置的数字交换如下图交换之后的结果如下如再在剩下的三个数字中找到最小的那个数字跟第个位置的数字交换位置上图中剩下的三个数字中最小的就是第个位置的数字所以它自己跟自己交换位置就是不变同理第四个数字也是不变第个数字也是不变上图中例子第个元素正好就是对应的排序所以不变如果不是对应的最小数字同理交换位置就行以上就是选择排序的算法逻辑代码实现最小值下标初始默认假设第一个数字就是最小数字如果找到更小的数字将变量的值修改为新的最小数字的下标选择排序小结选择排序是一种简单的排序算法适用于数据量较小的情况因为根据时间复杂度分析数据量越大选择排序所花费的时间按照平方倍数增长会非常慢但是选择排序也有它的优势选择排序的优势就是思维逻辑简单选择排序还有个特点就是不论数组的顺序是排好序或者是乱序的选择排序都需要花费一样的时间来计算比如利用选择排序对数组和数组排序所花费的时间是一样的插入排序概念插入排序将数组数据分成已排序区间和未排序区间有序区间和无序区间初始已排序区间只有一个元素即数组第一个元素从未排序区间取出一个元素插入到已排序区间新插入的元素要与已排序区间的数据一一比较大小直到该元素找到合适的位置陆续从未排序区间取出数据插入到已排序区间直到未排序区间为空实际操作过程中未排序区间的第一个元素与已排序区间的最后一个元素比较大小如果大于最后一个数据则不换位置直接加到已排序区间的末尾如果数据小于已排序区间的最后一个数据则需要换位并且该数据要与已排序区间前面的数据一一比较大小直到找到合适的位置原理有一个待排序的数组插入排序步骤如下初始时有序区间中只有无序区间中有将无序区间的插入到有序区间先比较和的大小比小则交换位置比较后有序区间中是无序区间中有再将加入到有序区间比较和的大小比小则交换位置此时有序区间是顺序正确如果顺序不正确还要与比较必须保证有序区间一定是排好序的此时无序区间中有再将加入到有序区间比较和的大小比大则无需交换位置直接将放在有序区间的末尾此时有序区间是此时无序区间中有再将加入到有序区间比较和的大小比小则交换位置与交换位置后有序区间的顺序还是不正确需要继续调整再与之前的数据一一比较直到找到合适的位置此时有序区间是此时无序区间中有再将加入到有序区间比较和的大小比小则交换位置与交换位置后有序区间的顺序还是不正确需要继续调整再与之前的数据一一比较直到找到合适的位置此时有序区间是此时无序区间有空当无序区间为空也就意味着排序结束最终排序结果为代码实现以上插入排序的代码实现代码中的第二个循环是重点第二个循环是只比较当前数据左边的值如果比左边的值小则交换位置否则位置不变插入排序小结插入排序适合如下类型的数组数组中的每一个元素距离其最终的位置都不远比如这个数组中最终位置应该是第一个位置此时的位置距离第一个位置不远一个有序的大数组中融入一个小数组比如有序大数组融入一个小数组数组中只有几个元素的位置不正确上述这三种情况的数组适合使用插入排序算法打过麻将的同学可以想想打麻将过程中不停地摸牌打牌整理牌的过程是不是就是一次插入排序呢排序是算法的基础排序的用途很多快速排序概念快速排序是对冒泡排序的一种改进由霍尔在年提出同冒泡排序一样快速排序也属于交换排序算法通过元素之间的比较和交换位置来达到排序的目的原理通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列快速排序与冒泡排序不同的是冒泡排序在每一轮中只把个元素冒泡到数列的一端而快速排序每次排序的时候设置一个基准点将小于等于基准点的数全部放到基准点的左边将大于等于基准点的数全部放到基准点的右边这样每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换交换的距离就得到提升快速排序之所比较快因为相比冒泡排序每次交换是跳跃式的这样总的比较和交换次数就少了速度自然就提高了快速排序在最坏的情况下仍可能是相邻的两个数进行了交换因此快速排序的最差时间复杂度和冒泡排序是一样的都是它的平均时间复杂度为快速排序这种思路就就是分治法步骤快速排序一般基于递归实现其步骤是这样的选定一个合适的值理想情况中值最好但实现中一般使用数组第一个值称为基准元素基于基准元素将数组分为两部分较小的分在左边较大的分在右边第一轮下来这个基准元素的位置一定在最终位置上对两个子数组分别重复上述过程直到每个数组只有一个元素排序完成总结快速排序其实就是给基准元素找其正确索引位置的过程注意快速排序算法有双边循环法和单边循环法双边循环法首先选定基准元素并且设置两个指针和指向数列的最左和最右两个元素从指针开始让指针所指向的元素和基准元素做比较指向的数据如果小于则指针停止移动切换到指针否则指针向左移动轮到指针行动让指针所指向的元素和基准元素做比较指向的数据如果大于则指针停止移动否则指针继续向右移动左右指针指向的元素交换位置指针当前指向的数据小于指针停止轮到指针移动由于开始指向的是基准元素所以右移位右移一位是由于所以指针停下这时和指针所指向的元素进行交换接下来重新切换到指针向左移动指针先移动到继续左移指向到由于停止在的位置第一轮下来数组为本轮下来本轮的基准元素的位置就是最终排序完成应该放置的位置接下来采用递归的方式分别对之前的前半部分排序再对后面的后半部分排序代码实现根据基准元素分成两部分进行递归排序取第个位置也可以选择随机位置的元素作为基准元素控制指针比较并左移控制指针比较并右移交换和指针所指向的元素交换和指针所指向的元素单边循环法单边循环法只从数组的一边对元素进行遍历和交换开始和双边循环法相似首先选定基准元素同时设置一个指针指向数列起始位置这个指针代表小于基准元素的区域边界接下来从基准元素的下一个位置开始遍历数组如果遍历到的元素大于基准元素就继续往后遍历如果遍历到的元素小于基准元素则需要做两件事第一把指针右移位因为小于的区域边界增大了第二让最新遍历到的元素和指针所在位置的元素交换位置因为最新遍历的元素归属于小于的区域首先遍历到元素所以继续遍历接下来遍历到的元素是所以指针右移位随后让元素和指针所在位置的元素交换因为元素归属于小于的区域按照这个思路继续遍历后续步骤如图所示代码实现快速排序之单边循环法根据基准元素分成两部分进行递归排序取第个位置也可以选择随机位置的元素作为基准元素希尔排序概念希尔排序是插入排序的一种又称缩小增量排序是直接插入排序算法的一种更高效的改进版本希尔排序是非稳定排序算法该方法因于年提出而得名希尔排序是基于插入排序的以下两点性质而提出改进方法的插入排序本身还不够高效插入排序每次只能将数据移动一位当有大量数据需要排序时会需要大量的移位操作但是插入排序在对几乎已经排好序的数据操作时效率很高几乎可以达到线性排序的效率所以如果能对数据进行初步排列后再用插入排序那么就会大大提高效率希尔排序是把记录按下标的一定增量分组对每组使用直接插入排序算法排序当增量减至时整个文件恰被分成一组算法便终止由于多次插入排序我们知道一次插入排序是稳定的不会改变相同元素的相对顺序但在不同的插入排序过程中相同的元素可能在各自的插入排序中移动最后其稳定性就会被打乱所以排序是不稳定的原理把元素按步长分组对每组元素采用直接插入排序方法进行排序随着步长逐渐减小所分成的组包含的元素越来越多当步长值减小到时整个数据合成一组构成一组有序记录完成排序代码实现希尔排序优劣优点算法较简单代码短需要的空间小速度还可以适合中小规模的排序缺点速度偏慢不够智能不适合情况简单的排序不适合大规模排序希尔排序稳定性希尔排序是不稳定的算法它满足稳定算法的定义对于相同的两个数可能由于分在不同的组中而导致它们的顺序发生变化算法稳定性假设在数列中存在若在排序之前在前面并且排序之后仍然在前面则这个排序算法是稳定的归并排序概念归并排序是一类与插入排序交换排序选择排序不同的另一种排序方法归并排序是采用分治法的一个非常典型的应用归并排序的思想就是先递归分解数组再合并数组将数组分解最小之后然后合并两个有序数组基本思路是比较两个数组的最前面的数谁小就先取谁取了后相应的指针就往后移一位然后再比较直至一个数组为空最后把另一个数组的剩余部分复制过来即可归并排序有多路归并排序两路归并排序可用于内排序也可以用于外排序原理分而治之每个递归过程涉及三个步骤第一分解把待排序的个元素的序列分解成两个子序列每个子序列包括个元素第二治理对每个子序列分别调用归并排序进行递归操作第三合并合并两个排好序的子序列生成排序结果归并排序图片演示代码实现左右归并把较小的数先移到新数组中把左边剩余的数移入数组把右边边剩余的数移入数组把新数组中的元素覆盖数组桶排序概念桶排序顾名思义会用到桶核心思想是将要排序的数据分到几个有序的桶里每个桶里的数据单独进行排序桶内排完序之后再把每个桶里的数据按照顺序依次取出组成的序列就是有序的了桶排序同样是一种线性时间的排序算法桶排序需要创建若干个桶来协助排序每一个桶代表一个区间范围里面可以承载一个或多个元素除了对一个桶内的元素做链表存储也有可能对每个桶中的元素继续使用其他排序算法进行排序所以更多时候桶排序会结合其他排序算法一起使用桶排序对排序的数据要求苛刻要排序的数据需要很容易就能划分成个桶并且桶与桶之间有着天然的大小顺序数据在各个桶之间的分布是比较均匀的桶排序比较适合用在外部排序中所谓的外部排序就是数据存储在外部磁盘中数据量比较大内存有限无法将数据全部加载到内存中原理桶排序的第步就是创建这些桶并确定每一个桶的区间范围具体需要建立多少个桶如何确定桶的区间范围有很多种不同的方式我们这里创建的桶数量等于原始数列的元素数量除最后一个桶只包含数列最大值外前面各个桶的区间按照比例来确定区间跨度最大值最小值桶的数量假设有一个非整数数列如下桶的个数为计算出区间跨度为序列区间跨度最大值最小值桶的数量区间跨度号桶中号桶中号桶中号桶中空号桶中如何计算当前数据属于某个区间或者说在哪个桶里桶编号元素数值最小值区间跨度遍历原始数列把元素对号入座放入各个桶中对每个桶内部的元素分别进行排序显然只有第个桶需要排序遍历所有的桶输出所有元素代码实现桶排序获取最大值和最小值获取桶个数计算区间跨度最大值最小值桶的数量桶的初始化循环获取元素应该放在哪个区间内也就是获取桶的编号获取当前数据应该放在哪个区间内也就是获取桶的编号对每个桶内部进行排序将数据回填到原数组中基数排序概念基数排序是桶排序的扩展是年赫尔曼何乐礼发明的基数排序的基本实现原理是将整数按位切割成不同的数字然后按位数进行比较基数排序是经典的空间换时间的算法占用内存很大当对海量数据排序时容易造成原理有一串数值如下所示首先根据个位数的数值将它们分配至编号到的桶子中将这些桶子中的数值重新串接起来成为的数列为接着再进行一次分配这次是根据十位数来分配将这些桶子中的数值重新串接起来成为的数列为这时候整个数列已经排序完毕如果排序的对象有三位数以上则持续进行以上的动作直至最高位数为止代码实现基数排序的实现有两种方式低位优先法适用于位数较小的数排序简称高位优先法适用于位数较多的情况简称的基数排序适用于位数小的数列如果位数多的话使用的效率会比较好的方式与相反是由高位数为基底开始进行分配但在分配之后并不马上合并回一个数组中而是在每个桶子中建立子桶将每个桶子中的数值按照下一数位的值分配到子桶中在进行完最低位数的分配后再合并回单一的数组中基数排序获取最大值获取最大值的位数目的用来判断需要进行几轮基数排序定义个桶容器数组的第一维表示二维下标按照最大可能来计算创建桶计数器记录每个桶中放置数据的个数数组元素共个表示个桶数组索引表示桶的编号索引对应的数值是该桶中的数据个数是记录重复操作轮数的计数器重复次数取决了最大数值的位数循环中定义变量用来表示位数表示个位表示十位表示百位目的是获取数字每个位上的值遍历数值放到桶中获取元素个位十位百位上的数字就是桶编号将数值放入桶中桶计数器增加数组索引下标每轮结束都要形成新的数列数组下标重新记录从个桶中取出数据形成新的数列判断桶中是否有数据遍历完数据将计数器清空下次重新计数计数排序概念计数排序这种排序算法是利用数组下标来确定元素的正确位置的计数排序是基本的桶排序定义个桶每个桶一个编号数据放到相应编号的桶中定义一个数组数组索引表示桶的编号索引值就是存放的数值如果该值为说明只出现一次如果大于说明重复多次出现计数排序是典型的空间换时间的算法原理假设数组中有个整数取值范围为要求用最快的速度把这个整数从小到大进行排序可以根据这有限的范围建立一个长度为的数组数组下标从到元素初始值全为假设数组数据为下面就开始遍历这个无序的随机数列每一个整数按照其值对号入座同时对应数组下标的元素进行加操作最终当数列遍历完毕时数组的状态如下该数组中每一个下标位置所对应的值其实就是数列中对应整数出现的次数直接遍历数组输出数组元素的下标值元素的值就是输出的次数不输出输出如果起始数不是从开始比如以下数列数组起始数为就采用偏移量的方式来排序数组遍历完毕数组的状态如下原本输出增加上偏移量后实际应该顺序输出为代码实现计数排序获取最大值和最小值计算桶的数量创建桶数组遍历原数组计算元素在桶中的编号桶上计数累加将数据回填到原数组中实际数值桶编号最小数值全班个人最低成绩分最高成绩分将这些成绩进行排序随机生成个成绩堆排序概念堆是具有以下性质的完全二叉树大顶堆每个节点的值都大于或等于其左右孩子节点的值小顶堆每个结点的值都小于或等于其左右孩子结点的值对堆中的结点按层进行编号将这种逻辑结构映射到数组中该数组从逻辑上讲就是一个堆结构用简单的公式来描述一下堆的定义就是大顶堆小顶堆原理将待排序序列构造成一个大顶堆此时整个序列的最大值就是堆顶的根节点将其与末尾元素进行交换此时末尾就为最大值然后将剩余个元素重新构造成一个堆这样会得到个元素的次小值如此反复执行便能得到一个有序序列了构造初始堆将给定无序序列构造成一个大顶堆一般升序采用大顶堆降序采用小顶堆此时从最后一个非叶子节点开始叶子节点自然不用调整第一个非叶子节点也就是下面的结点从左至右从下至上进行调整找到第二个非叶节点由于中元素最大和交换这时交换导致了子根结构混乱继续调整中最大交换和此时我们就将一个无序序列构造成了一个大顶堆将堆顶元素与末尾元素进行交换使末尾元素最大然后继续调整堆再将堆顶元素与末尾元素交换得到第二大元素如此反复进行交换重建交换将堆顶元素和末尾元素进行交换重新调整结构使其继续满足大顶堆再将堆顶元素与末尾元素进行交换得到第二大元素继续进行调整成大顶堆顶部的与右子树的交换最终使得整个序列有序代码实现堆排序构建堆堆顶与末尾元素调换将堆顶元素下沉目的是将最大元素上浮到堆顶左边节点下标右边节点下标父节点下标下沉左边下沉右边继续下沉概念排序算法是双基准元素快速排序由弗拉基米尔雅罗斯拉夫斯基乔恩本特利和约书亚布洛克提供该算法在许多数据集上表现出的时间复杂度比传统的单基准元素快速排序算法性能更快原理在微小数组上使用插入排序如果要排序的数组长度小于这个常量则插入排序优先于快速排序对小数组使用快速排序如果要排序的数组长度小于这个常量则快速排序优先于归并排序数组接近排序使用归并排序归并排序的最大运行次数归并排序运行的最大长度数组不是高度结构化的使用快速排序代替归并排序对大数组使用计数排序如果要排序的字节数组的长度大于该常量则优先使用计数排序而不是插入排序对大数组使用计数排序如果要排序的短数组或数组的长度大于该常量则优先使用计数排序而不是快速排序源码截图在微小数组上使用插入排序对小数组使用快速排序数组接近排序使用归并排序对大数组使用计数排序对大数组使用计数排序排序算法与复杂度归类注学习完时间复杂度和空间复杂度的内容再做一下学习根据时间复杂度的不同主流的排序算法可以分为大类时间复杂度为的排序算法冒泡排序选择排序插入排序冒选插时间复杂度为的排序算法快速排序堆排序希尔排序归并排序快堆希归时间复杂度为线性的排序算法桶排序计数排序基数排序桶计基各个排序算法比对表排序算法时间复杂度空间复杂度是否稳定比较次数冒泡排序平均最差稳定未优化无序有序优化有序优化最差选择排序平均最差不稳定无序有序固定插入排序平均最差稳定有序无序最差快速排序平均最差不稳定属于交换排序堆排序平均最差不稳定属于选择排序希尔排序平均最好不稳定归并排序平均最差稳定桶排序稳定适用于浮点数适用于外部排序计数排序稳定适合于连续的取值范围不大的数组基数排序平均最差为位数稳定处理海量数据排序时容易各种排序算法性能对比执行万个随机数的排序同一台机器相同条件下的测试结果冒泡选择插入快速堆希尔归并计数基数桶执行万个随机数的排序同一台机器相同条件下的测试结果冒泡选择插入快速堆希尔归并计数基数桶执行万个随机数的排序同一台机器相同条件下的测试结果冒泡选择插入快速堆希尔归并计数基数桶排序效率排名计数基数快速堆希尔归并桶插入选择冒泡根据其稳定性可以分为稳定排序和不稳定排序稳定排序值相同的元素在排序后仍然保持着排序前的顺序不稳定排序值相同的元素在排序后打乱了排序前的顺序选择快速堆希尔",isPost:!0,isHome:!1,isHighlightShrink:!1,isToc:!0,postUpdate:"2023-06-26 20:24:46",postMainColor:""}</script><noscript><style type="text/css">#nav{opacity:1}.justified-gallery img{opacity:1}#post-meta time,#recent-posts time{display:inline!important}</style></noscript><script>(e=>{e.saveToLocal={set:(e,t,a)=>{var o;0!==a&&(o=Date.now(),localStorage.setItem(e,JSON.stringify({value:t,expiry:o+864e5*a})))},get:e=>{var t=localStorage.getItem(e);if(t){t=JSON.parse(t);if(!(Date.now()>t.expiry))return t.value;localStorage.removeItem(e)}}},e.getScript=(o,c={})=>new Promise((t,e)=>{let a=document.createElement("script");a.src=o,a.async=!0,a.onerror=e,a.onload=a.onreadystatechange=function(){var e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(a.onload=a.onreadystatechange=null,t())},Object.keys(c).forEach(e=>{a.setAttribute(e,c[e])}),document.head.appendChild(a)}),e.getCSS=(o,c=!1)=>new Promise((t,e)=>{let a=document.createElement("link");a.rel="stylesheet",a.href=o,c&&(a.id=c),a.onerror=e,a.onload=a.onreadystatechange=function(){var e=this.readyState;e&&"loaded"!==e&&"complete"!==e||(a.onload=a.onreadystatechange=null,t())},document.head.appendChild(a)}),e.activateDarkMode=()=>{document.documentElement.setAttribute("data-theme","dark"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#18171d")},e.activateLightMode=()=>{document.documentElement.setAttribute("data-theme","light"),null!==document.querySelector('meta[name="theme-color"]')&&document.querySelector('meta[name="theme-color"]').setAttribute("content","#f7f9fe")};var e=saveToLocal.get("theme"),t=window.matchMedia("(prefers-color-scheme: dark)").matches,a=window.matchMedia("(prefers-color-scheme: light)").matches,o=window.matchMedia("(prefers-color-scheme: no-preference)").matches,c=!t&&!a&&!o,t=(void 0===e?(a?activateLightMode():t?activateDarkMode():(o||c)&&((a=(new Date).getHours())<=6||18<=a?activateDarkMode:activateLightMode)(),window.matchMedia("(prefers-color-scheme: dark)").addListener(e=>{void 0===saveToLocal.get("theme")&&(e.matches?activateDarkMode:activateLightMode)()})):("light"===e?activateLightMode:activateDarkMode)(),saveToLocal.get("aside-status"));void 0!==t&&("hide"===t?document.documentElement.classList.add("hide-aside"):document.documentElement.classList.remove("hide-aside"));/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)&&document.documentElement.classList.add("apple")})(window)</script><meta name="generator" content="Hexo 7.3.0"><link rel="alternate" href="/atom.xml" title="InsectMk的个人空间" type="application/atom+xml"><link rel="alternate" href="/rss2.xml" title="InsectMk的个人空间" type="application/rss+xml"></head><body data-type="anzhiyu"><div id="web_bg"></div><div id="an_music_bg"></div><div id="loading-box" onclick="document.getElementById(&quot;loading-box&quot;).classList.add(&quot;loaded&quot;)"><div class="loading-bg"><img class="loading-img nolazyload" alt="加载头像" src="/static/img/head/insectmk.jpg"><div class="loading-image-dot"></div></div></div><script>let preloader={endLoading:()=>{document.getElementById("loading-box").classList.add("loaded")},initLoading:()=>{document.getElementById("loading-box").classList.remove("loaded")}};window.addEventListener("load",()=>{preloader.endLoading()}),setTimeout(function(){preloader.endLoading()},1e4),document.addEventListener("pjax:send",()=>{preloader.initLoading()}),document.addEventListener("pjax:complete",()=>{preloader.endLoading()})</script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.1.10/progress_bar/progress_bar.css"><script async src="https://cdn.cbd.int/pace-js@1.2.4/pace.min.js" data-pace-options="{ &quot;restartOnRequestAfter&quot;:false,&quot;eventLag&quot;:false}"></script><div class="post" id="body-wrap"><header class="not-top-img" id="page-header"><nav id="nav"><div id="nav-group"><span id="blog_name"><div class="back-home-button"><i class="anzhiyufont anzhiyu-icon-grip-vertical"></i><div class="back-menu-list-groups"><div class="back-menu-list-group"><div class="back-menu-list-title">网页</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://insectmk.cn/" title="主博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="主博客"><span class="back-menu-item-text">主博客</span></a><a class="back-menu-item" href="https://insectmk.top/" title="次博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="次博客"><span class="back-menu-item-text">次博客</span></a></div></div><div class="back-menu-list-group"><div class="back-menu-list-title">项目</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://gitee.com/insectmk/chatbot-web" title="智能聊天机器人网站"><img class="back-menu-item-icon" src="https://image.insectmk.cn/hexo-gitee-blog/project/icon/chatbot-web.jpg" alt="智能聊天机器人网站"><span class="back-menu-item-text">智能聊天机器人网站</span></a></div></div></div></div><a id="site-name" href="/" accesskey="h"><div class="title">InsectMk的个人空间</div><i class="anzhiyufont anzhiyu-icon-house-chimney"></i></a></span><div class="mask-name-container"><div id="name-container"><a id="page-name" href="javascript:anzhiyu.scrollToDest(0, 500)">PAGE_NAME</a></div></div><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-home"></use></svg><span>主页</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-hand-peace"></use></svg><span>娱乐</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/entertainment/gallery/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-images"></use></svg><span>图库</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-comments"></use></svg><span>交流</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/contact/comments/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-paper-plane"></use></svg><span>留言板</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/contact/link/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-link"></use></svg><span>友链</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-compass"></use></svg><span>目录</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/categories/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-archive"></use></svg><span>分类</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/tags/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-tags"></use></svg><span>标签</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/archives/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-folder-open"></use></svg><span>归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-server"></use></svg><span>服务</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/server/left4dead2/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-icons-left__dead_"></use></svg><span>求生之路</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/server/minecraft/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-minecraft"></use></svg><span>我的世界</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-clipboard"></use></svg><span>日志</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/log/website/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-website-with-different-sections"></use></svg><span>个人网站</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/log/pc/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-desktop"></use></svg><span>个人电脑</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-bars"></use></svg><span>其他</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/extend/remind/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-note"></use></svg><span>备忘</span></a></li></ul></div><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/about/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-id-card"></use></svg><span>关于</span></a></div></div></div><div id="nav-right"><div class="nav-button" id="randomPost_button"><a class="site-page" onclick="toRandomPost()" title="随机前往一个文章" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-dice"></i></a></div><div class="nav-button" id="search-button"><a class="site-page social-icon search" href="javascript:void(0);" title="搜索🔍" accesskey="s"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span> 搜索</span></a></div><input id="center-console" type="checkbox"><label class="widget" for="center-console" title="中控台" onclick="anzhiyu.switchConsole()"><i class="left"></i><i class="widget center"></i><i class="widget right"></i></label><div id="console"><div class="console-card-group-reward"><ul class="reward-all console-card"><li class="reward-item"><a href="/static/img/website/reward/wechat.png" target="_blank"><img class="post-qr-code-img" alt="微信" src="/static/img/website/reward/wechat.png"></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/static/img/website/reward/alipay.png" target="_blank"><img class="post-qr-code-img" alt="支付宝" src="/static/img/website/reward/alipay.png"></a><div class="post-qr-code-desc">支付宝</div></li></ul></div><div class="console-card-group"><div class="console-card-group-left"><div class="console-card" id="card-newest-comments"><div class="card-content"><div class="author-content-item-tips">互动</div><span class="author-content-item-title">最新评论</span></div><div class="aside-list"><span>正在加载中...</span></div></div></div><div class="console-card-group-right"><div class="console-card tags"><div class="card-content"><div class="author-content-item-tips">兴趣点</div><span class="author-content-item-title">寻找你感兴趣的领域</span><div class="card-tags"><div class="item-headline"></div><div class="card-tag-cloud"><a href="/tags/AOP/" style="font-size:1.05rem">AOP<sup>1</sup></a><a href="/tags/Butterfly/" style="font-size:1.05rem">Butterfly<sup>4</sup></a><a href="/tags/Docker/" style="font-size:1.05rem">Docker<sup>6</sup></a><a href="/tags/ElementUI/" style="font-size:1.05rem">ElementUI<sup>1</sup></a><a href="/tags/Frp/" style="font-size:1.05rem">Frp<sup>1</sup></a><a href="/tags/Hexo/" style="font-size:1.05rem">Hexo<sup>8</sup></a><a href="/tags/IntelliJ-IDEA/" style="font-size:1.05rem">IntelliJ IDEA<sup>1</sup></a><a href="/tags/JDK/" style="font-size:1.05rem">JDK<sup>1</sup></a><a href="/tags/JWT/" style="font-size:1.05rem">JWT<sup>1</sup></a><a href="/tags/Java/" style="font-size:1.05rem">Java<sup>35</sup></a><a href="/tags/Junit/" style="font-size:1.05rem">Junit<sup>1</sup></a><a href="/tags/Leanote/" style="font-size:1.05rem">Leanote<sup>1</sup></a><a href="/tags/Maven/" style="font-size:1.05rem">Maven<sup>2</sup></a><a href="/tags/MyBatisPlus/" style="font-size:1.05rem">MyBatisPlus<sup>1</sup></a><a href="/tags/MySQL5-7/" style="font-size:1.05rem">MySQL5.7<sup>1</sup></a><a href="/tags/Mybatis/" style="font-size:1.05rem">Mybatis<sup>1</sup></a><a href="/tags/MybatisPlus/" style="font-size:1.05rem">MybatisPlus<sup>1</sup></a><a href="/tags/OSS/" style="font-size:1.05rem">OSS<sup>1</sup></a><a href="/tags/Spring/" style="font-size:1.05rem">Spring<sup>2</sup></a><a href="/tags/Spring-Boot/" style="font-size:1.05rem">SpringBoot<sup>6</sup></a><a href="/tags/Vue2/" style="font-size:1.05rem">Vue2<sup>9</sup></a><a href="/tags/Vue3/" style="font-size:1.05rem">Vue3<sup>1</sup></a><a href="/tags/Vuetify/" style="font-size:1.05rem">Vuetify<sup>1</sup></a><a href="/tags/Vuex/" style="font-size:1.05rem">Vuex<sup>1</sup></a><a href="/tags/Waline/" style="font-size:1.05rem">Waline<sup>3</sup></a><a href="/tags/mvc/" style="font-size:1.05rem">mvc<sup>3</sup></a><a href="/tags/mybatis/" style="font-size:1.05rem">mybatis<sup>1</sup></a><a href="/tags/profile/" style="font-size:1.05rem">profile<sup>1</sup></a><a href="/tags/spring/" style="font-size:1.05rem">spring<sup>5</sup></a><a href="/tags/springboot/" style="font-size:1.05rem">springboot<sup>4</sup></a><a href="/tags/transaction/" style="font-size:1.05rem">transaction<sup>1</sup></a><a href="/tags/yaml/" style="font-size:1.05rem">yaml<sup>2</sup></a><a href="/tags/%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/" style="font-size:1.05rem">个人博客<sup>11</sup></a><a href="/tags/%E4%BA%8B%E5%8A%A1/" style="font-size:1.05rem">事务<sup>1</sup></a><a href="/tags/%E5%88%86%E9%A1%B5/" style="font-size:1.05rem">分页<sup>1</sup></a><a href="/tags/%E5%89%8D%E7%AB%AF/" style="font-size:1.05rem">前端<sup>1</sup></a><a href="/tags/%E6%9C%8D%E5%8A%A1%E5%99%A8/" style="font-size:1.05rem">服务器<sup>20</sup></a><a href="/tags/%E6%AF%95%E4%B8%9A%E8%AE%BE%E8%AE%A1/" style="font-size:1.05rem">毕业设计<sup>14</sup></a><a href="/tags/%E7%A6%85%E9%81%93/" style="font-size:1.05rem">禅道<sup>1</sup></a><a href="/tags/%E7%BB%BF%E8%89%B2%E8%A7%A3%E5%8E%8B/" style="font-size:1.05rem">绿色解压<sup>1</sup></a></div></div><hr></div></div><div class="console-card history"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-box-archiv"></i><span>文章</span></div><div class="card-archives"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-archive"></i><span>归档</span><a class="card-more-btn" href="/archives/" title="查看更多"> <i class="anzhiyufont anzhiyu-icon-angle-right"></i></a></div><ul class="card-archive-list"><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/07/"><span class="card-archive-list-date">七月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">4</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/06/"><span class="card-archive-list-date">六月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">1</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/05/"><span class="card-archive-list-date">五月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">4</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/04/"><span class="card-archive-list-date">四月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">8</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/03/"><span class="card-archive-list-date">三月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">9</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/02/"><span class="card-archive-list-date">二月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">5</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/01/"><span class="card-archive-list-date">一月 2024</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">5</span><span>篇</span></div></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2023/10/"><span class="card-archive-list-date">十月 2023</span><div class="card-archive-list-count-group"><span class="card-archive-list-count">8</span><span>篇</span></div></a></li></ul></div><hr></div></div></div><div class="button-group"><div class="console-btn-item"><a class="darkmode_switchbutton" title="显示模式切换" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-moon"></i></a></div><div class="console-btn-item" id="consoleHideAside" onclick="anzhiyu.hideAsideBtn()" title="边栏显示控制"><a class="asideSwitch"><i class="anzhiyufont anzhiyu-icon-arrows-left-right"></i></a></div><div class="console-btn-item" id="consoleMusic" onclick="anzhiyu.musicToggle()" title="音乐开关"><a class="music-switch"><i class="anzhiyufont anzhiyu-icon-music"></i></a></div></div><div class="console-mask" onclick="anzhiyu.hideConsole()" href="javascript:void(0);"></div></div><div class="nav-button" id="nav-totop"><a class="totopbtn" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i><span id="percent" onclick="anzhiyu.scrollToDest(0,500)">0</span></a></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);" title="切换"><i class="anzhiyufont anzhiyu-icon-bars"></i></a></div></div></div></nav></header><main id="blog-container"><div class="layout" id="content-inner"><div id="post"><div id="post-info"><div id="post-firstinfo"><div class="meta-firstline"><a class="post-meta-original">原创</a><span class="post-meta-categories"><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-inbox post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%95%99%E8%82%B2/" itemprop="url">教育</a></span><span class="article-meta tags"><a class="article-meta__tags" href="/tags/Java/" tabindex="-1" itemprop="url"> <span><i class="anzhiyufont anzhiyu-icon-hashtag"></i>Java</span></a><a class="article-meta__tags" href="/tags/%E5%8D%83%E9%94%8B%E6%95%99%E8%82%B2/" tabindex="-1" itemprop="url"> <span><i class="anzhiyufont anzhiyu-icon-hashtag"></i>千锋教育</span></a><a class="article-meta__tags" href="/tags/%E5%9F%B9%E8%AE%AD/" tabindex="-1" itemprop="url"> <span><i class="anzhiyufont anzhiyu-icon-hashtag"></i>培训</span></a></span></div></div><h1 class="post-title" itemprop="name headline">数据的排序</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="anzhiyufont anzhiyu-icon-calendar-days post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" itemprop="dateCreated datePublished" datetime="2023-06-26T12:24:46.000Z" title="发表于 2023-06-26 20:24:46">2023-06-26</time><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-history post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" itemprop="dateCreated datePublished" datetime="2023-06-26T12:24:46.000Z" title="更新于 2023-06-26 20:24:46">2023-06-26</time></span></div><div class="meta-secondline"><span class="post-meta-separator"></span><span class="post-meta-wordcount"><i class="anzhiyufont anzhiyu-icon-file-word post-meta-icon" title="文章字数"></i><span class="post-meta-label" title="文章字数">字数总计:</span><span class="word-count" title="文章字数">10.9k</span><span class="post-meta-separator"></span><i class="anzhiyufont anzhiyu-icon-clock post-meta-icon" title="阅读时长"></i><span class="post-meta-label" title="阅读时长">阅读时长:</span><span>39分钟</span></span><span class="post-meta-separator"></span><span data-flag-title="数据的排序"><i class="anzhiyufont anzhiyu-icon-fw-eye post-meta-icon"></i><span class="post-meta-label" title="阅读量">阅读量:</span><span class="waline-pageview-count" data-path="/posts/1a656c15/" title="访问量"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-spin"></i></span></span><span class="post-meta-separator"> </span><span class="post-meta-position" title="作者IP属地为成都"><i class="anzhiyufont anzhiyu-icon-location-dot"></i>成都</span><span class="post-meta-separator"></span><span class="post-meta-commentcount"><i class="anzhiyufont anzhiyu-icon-comments post-meta-icon"></i><span class="post-meta-label">评论数:</span><a href="/posts/1a656c15/#post-comment"><span class="waline-comment-count" data-path="/posts/1a656c15/"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-spin"></i></span></a></span></div></div></div><article class="post-content" id="article-container" itemscope itemtype="https://insectmk.top/posts/1a656c15/"><header><a class="post-meta-categories" href="/categories/%E6%95%99%E8%82%B2/" itemprop="url">教育</a><a href="/tags/Java/" tabindex="-1" itemprop="url">Java</a><a href="/tags/%E5%8D%83%E9%94%8B%E6%95%99%E8%82%B2/" tabindex="-1" itemprop="url">千锋教育</a><a href="/tags/%E5%9F%B9%E8%AE%AD/" tabindex="-1" itemprop="url">培训</a><h1 id="CrawlerTitle" itemprop="name headline">数据的排序</h1><span itemprop="author" itemscope itemtype="http://schema.org/Person">InsectMk</span><time itemprop="dateCreated datePublished" datetime="2023-06-26T12:24:46.000Z" title="发表于 2023-06-26 20:24:46">2023-06-26</time><time itemprop="dateCreated datePublished" datetime="2023-06-26T12:24:46.000Z" title="更新于 2023-06-26 20:24:46">2023-06-26</time></header><h1 id="数组的排序"><a href="#数组的排序" class="headerlink" title="数组的排序"></a>数组的排序</h1><h2 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h2><h3 id="排序概念"><a href="#排序概念" class="headerlink" title="排序概念"></a>排序概念</h3><blockquote><p>排序是将一组数据，依据指定的顺序进行排列的过程。</p><p>排序是算法中的一部分，也叫排序算法。算法处理数据，而数据的处理最好是要找到他们的规律，这个规律中有很大一部分就是要进行排序，所以需要有排序算法。</p></blockquote><h3 id="常见的排序算法分类"><a href="#常见的排序算法分类" class="headerlink" title="常见的排序算法分类"></a>常见的排序算法分类</h3><blockquote><p>排序分为：内部排序和外部排序。</p><ul><li>内部排序：是将需要处理的所有数据加载到内存中进行排序；</li><li>外部排序：当数据量过大，无法全部加载到内存中，需要借助外部存储（文件、磁盘等）进行排序。</li></ul></blockquote><blockquote><ul><li>交换排序（冒泡排序、快速排序）</li><li>选择排序（选择排序、堆排序）</li><li>插入排序（插入排序、希尔排序）</li><li>归并排序</li><li>桶排序、 计数排序、基数排序</li></ul></blockquote><h3 id="算法稳定性"><a href="#算法稳定性" class="headerlink" title="算法稳定性"></a>算法稳定性</h3><blockquote><p>假设在数列中存在a[i]&#x3D;a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面，则这个排序算法是稳定的。</p></blockquote><h3 id="如何分析算法"><a href="#如何分析算法" class="headerlink" title="如何分析算法"></a>如何分析算法</h3><h4 id="分析算法的执行效率"><a href="#分析算法的执行效率" class="headerlink" title="分析算法的执行效率"></a>分析算法的执行效率</h4><blockquote><ol><li>最好、最坏、平均情况时间复杂度。</li><li>时间复杂度的系数、常数和低阶。</li><li>比较次数，交换（或移动）次数。</li></ol></blockquote><h4 id="分析排序算法的稳定性"><a href="#分析排序算法的稳定性" class="headerlink" title="分析排序算法的稳定性"></a>分析排序算法的稳定性</h4><blockquote><p>概念：如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。</p><p>稳定性重要性：可针对对象的多种属性进行有优先级的排序。</p><p>举例：给电商交易系统中的“订单”排序，按照金额大小对订单数据排序，对于相同金额的订单以下单时间早晚排序。用稳定排序算法可简洁地解决。先按照下单时间给订单排序，排序完成后用稳定排序算法按照订单金额重新排序。</p></blockquote><h4 id="分析排序算法的内存损耗"><a href="#分析排序算法的内存损耗" class="headerlink" title="分析排序算法的内存损耗"></a>分析排序算法的内存损耗</h4><blockquote><p>原地排序算法：特指空间复杂度是O(1)的排序算法。</p></blockquote><h2 id="冒泡排序"><a href="#冒泡排序" class="headerlink" title="冒泡排序"></a>冒泡排序</h2><h3 id="概念"><a href="#概念" class="headerlink" title="概念"></a>概念</h3><blockquote><p>冒泡排序是最基础的排序算法。属于交换排序算法。</p><p>冒泡排序重复地遍历要排序的数组元素，一次比较两个元素，如果他们的顺序错误就把他们交换过来。重复地进行直到没有再需要交换，也就是说该数组已经排序完成。</p><p>这个算法的名字由来是因为越大的元素会经过交换慢慢“浮”到数列的顶端，故名“冒泡排序”。</p><p>按照冒泡排序的思想，把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换它们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。</p><p>冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求，如果不满足就让它俩互换。</p></blockquote><h3 id="原理"><a href="#原理" class="headerlink" title="原理"></a>原理</h3><blockquote><ol><li>比较相邻的元素。如果第一个比第二个大，就交换他们两个。</li><li>对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</li><li>针对所有的元素重复以上的步骤，除了最后一个。</li><li>持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/冒泡排序1.png" style="zoom:33%"><blockquote><p>经过第一轮后: 元素9作为数列中最大的元素，就像是汽水里的小气泡一样，“漂”到了最右侧。</p></blockquote><blockquote><p>每一轮结束都会有一个元素被移到最右侧。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/冒泡排序3.png" style="zoom:33%"><h3 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">5</span>, <span class="number">8</span>, <span class="number">6</span>, <span class="number">3</span>, <span class="number">9</span>, <span class="number">2</span>, <span class="number">1</span>, <span class="number">7</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length-<span class="number">1</span>; i++) &#123;</span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; arr.length-<span class="number">1</span>-i; j++) &#123;</span><br><span class="line">				<span class="keyword">if</span>(arr[j] &gt; arr[j+<span class="number">1</span>])&#123;</span><br><span class="line">                    <span class="comment">//通过第三方变量实现两个变量的交换</span></span><br><span class="line">                    <span class="comment">//缺点：需要声明变量</span></span><br><span class="line">					<span class="comment">//int temp = arr[j];</span></span><br><span class="line">					<span class="comment">//arr[j] = arr[j+1];</span></span><br><span class="line">					<span class="comment">//arr[j+1] = temp;</span></span><br><span class="line">                    </span><br><span class="line">                    <span class="comment">//通过两个变量加减实现两个变量的交换</span></span><br><span class="line">                    <span class="comment">//缺点：当两个变量相加超出int取值范围，会损失精度</span></span><br><span class="line">					<span class="comment">//arr[j] = arr[j] + arr[j+1] - (arr[j+1] = arr[j]);</span></span><br><span class="line">					</span><br><span class="line">					<span class="comment">//通过位运算^异或实现两个变量的交换</span></span><br><span class="line">					arr[j] = arr[j]^arr[j+<span class="number">1</span>];</span><br><span class="line">					arr[j+<span class="number">1</span>] = arr[j]^arr[j+<span class="number">1</span>];</span><br><span class="line">					arr[j] = arr[j]^arr[j+<span class="number">1</span>];</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="口诀"><a href="#口诀" class="headerlink" title="口诀"></a>口诀</h3><blockquote><p>N个数字来排队</p><p>两两相比小靠前</p><p>外层循环N-1</p><p>内层循环N-1-i</p></blockquote><h3 id="优化代码"><a href="#优化代码" class="headerlink" title="优化代码"></a>优化代码</h3><blockquote><p><strong>为什么需要优化？</strong></p><p>针对不同的数列，需要循环的轮数是有不同的。</p><p>例如：54321需要4轮循环之后才能排好序。而12345，当执行第一轮循环后，所有相邻的两个数值都无需换位，那说明排序正常，无需排序。不用执行后续的循环。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/优化冒泡排序1.png" style="zoom:33%"> <img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/优化冒泡排序2.png" style="zoom:30.5%"><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test02</span> &#123;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">5</span>, <span class="number">8</span>, <span class="number">6</span>, <span class="number">3</span>, <span class="number">9</span>, <span class="number">2</span>, <span class="number">1</span>, <span class="number">7</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length-<span class="number">1</span>; i++) &#123;</span><br><span class="line">			<span class="comment">//默认排好了</span></span><br><span class="line">			<span class="type">boolean</span> <span class="variable">isSort</span> <span class="operator">=</span> <span class="literal">true</span>;</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; arr.length-<span class="number">1</span>-i; j++) &#123;</span><br><span class="line">				<span class="keyword">if</span>(arr[j] &gt; arr[j+<span class="number">1</span>])&#123;</span><br><span class="line">					</span><br><span class="line">					isSort = <span class="literal">false</span>;</span><br><span class="line">					</span><br><span class="line">					arr[j] = arr[j]^arr[j+<span class="number">1</span>];</span><br><span class="line">					arr[j+<span class="number">1</span>] = arr[j]^arr[j+<span class="number">1</span>];</span><br><span class="line">					arr[j] = arr[j]^arr[j+<span class="number">1</span>];</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="comment">//排好了跳出循环</span></span><br><span class="line">			<span class="keyword">if</span>(isSort)&#123;</span><br><span class="line">				<span class="keyword">break</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="选择排序"><a href="#选择排序" class="headerlink" title="选择排序"></a>选择排序</h2><h3 id="概念-1"><a href="#概念-1" class="headerlink" title="概念"></a>概念</h3><blockquote><p>选择排序将数组分成已排序区间和未排序区间。初始已排序区间为空。每次从未排序区间中选出最小的元素放到已排序区间的末尾，直到未排序区间为空。</p></blockquote><h3 id="原理-1"><a href="#原理-1" class="headerlink" title="原理"></a>原理</h3><blockquote><p>选择排序是一种最简单的排序算法。其排序的逻辑如下:</p><ol><li>有一个待排序的数组A</li><li>从A中找出最小的元素。</li><li>将找到的最小元素跟数组A中第一个元素交换位置(如果最小元素就是第一个元素，则自己跟自己交换位置)。如下图:</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/选择排序1.png" style="zoom:13%"><blockquote><p>(如上图，长方形高低代表数字的大小，找到最小的数字，跟第一个位置的数据进行交换)</p><p>交换之后，结果如下图所示:</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/选择排序2.png" style="zoom:13%"><blockquote><ol start="4"><li>然后，在剩下的4个数字中再找到最小的那个数字，跟第2个位置的数字交换。如下图:</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/选择排序3.png" style="zoom:20%"><blockquote><p>交换之后的结果如下如:</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/选择排序4.png" style="zoom:20%"><blockquote><ol start="5"><li>再在剩下的三个数字中，找到最小的那个数字跟第3个位置的数字交换位置。上图中剩下的三个数字中最小的就是第3个位置的数字，所以，它自己跟自己交换位置，就是不变。同理第 四个数字也是不变，第5个数字也是不变。(上图中例子第3、4、5个元素正好就是对应的排 序，所以不变。如果不是对应的最小数字，同理交换位置就行。) 以上就是选择排序的算法逻辑。</li></ol></blockquote><h3 id="代码实现-1"><a href="#代码实现-1" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">5</span>, <span class="number">8</span>, <span class="number">6</span>, <span class="number">3</span>, <span class="number">9</span>, <span class="number">2</span>, <span class="number">1</span>, <span class="number">7</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">//最小值下标。初始默认假设第一个数字就是最小数字</span></span><br><span class="line">			<span class="type">int</span> <span class="variable">minIndex</span> <span class="operator">=</span> i;</span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> i+<span class="number">1</span>; j &lt; arr.length; j++) &#123;</span><br><span class="line">				<span class="comment">//如果找到更小的数字</span></span><br><span class="line">				<span class="keyword">if</span>(arr[minIndex] &gt; arr[j])&#123;</span><br><span class="line">					<span class="comment">//将minIndex变量的值修改为新的最小数字的下标</span></span><br><span class="line">					minIndex = j;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">			</span><br><span class="line">			<span class="keyword">if</span>(minIndex != i)&#123;</span><br><span class="line">				arr[minIndex] = arr[minIndex] ^ arr[i];</span><br><span class="line">				arr[i] = arr[minIndex] ^ arr[i];</span><br><span class="line">				arr[minIndex] = arr[minIndex] ^ arr[i];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="选择排序小结"><a href="#选择排序小结" class="headerlink" title="选择排序小结"></a>选择排序小结</h3><blockquote><p>选择排序是一种简单的排序算法，适用于数据量较小的情况，因为根据时间复杂度分析，数据量越大，选择排序所花费的时间按照平方倍数增长，会非常慢。</p><p>但是选择排序也有它的优势，选择排序的优势就是思维逻辑简单。</p><p>选择排序还有个特点，就是不论数组的顺序是排好序或者是乱序的，选择排序都需要花费一样的时间来计算。比如，利用选择排序对数组{1,2,3,4,5}和数组{3,1,4,2,5}排序所花费的时间是一样的。</p></blockquote><h2 id="插入排序"><a href="#插入排序" class="headerlink" title="插入排序"></a>插入排序</h2><h3 id="概念-2"><a href="#概念-2" class="headerlink" title="概念"></a>概念</h3><blockquote><p>插入排序将数组数据分成已排序区间和未排序区间（有序区间和无序区间）。</p><p>初始已排序区间只有一个元素，即数组第一个元素。从未排序区间取出一个元素插入到已排序区间，新插入的元素要与已排序区间的数据一一比较大小，直到该元素找到合适的位置。陆续从未排序区间取出数据插入到已排序区间，直到未排序区间为空。</p><p>实际操作过程中，未排序区间的第一个元素与已排序区间的最后一个元素比较大小，如果大于最后一个数据则不换位置，直接加到已排序区间的末尾。如果数据小于已排序区间的最后一个数据，则需要换位，并且该数据要与已排序区间前面的数据一一比较大小，直到找到合适的位置。</p></blockquote><h3 id="原理-2"><a href="#原理-2" class="headerlink" title="原理"></a>原理</h3><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/插入排序1.png" alt="image-20220731205457305" style="zoom:70%"><blockquote><p>有一个待排序的数组：5、2、4、6、1、3。插入排序步骤如下：</p><ol><li><p>初始时，有序区间中只有5，无序区间中有2、4、6、1、3。</p><p>将无序区间的2插入到有序区间，先比较2和5的大小。2比5小则交换位置。</p><p>比较后，有序区间中是2、5，无序区间中有4、6、1、3。</p></li><li><p>再将4加入到有序区间，比较4和5的大小。4比5小，则交换位置。此时有序区间是2、4、5，顺序正确。</p><p>如果顺序不正确，4还要与2比较，必须保证有序区间一定是排好序的。此时无序区间中有6、1、3。</p></li><li><p>再将6加入到有序区间，比较6和5的大小。6比5大，则无需交换位置，直接将6放在有序区间的末尾。此时有序区间是2、4、5、6，此时无序区间中有1、3。</p></li><li><p>再将1加入到有序区间，比较1和6的大小。1比6小，则交换位置。1与6交换位置后，有序区间的顺序还是不正确，需要继续调整，1再与之前的数据一一比较，直到找到合适的位置。此时有序区间是1、2、4、5、6，此时无序区间中有3。</p></li><li><p>再将3加入到有序区间，比较3和6的大小。3比6小，则交换位置。3与6交换位置后，有序区间的顺序还是不正确，需要继续调整，3再与之前的数据一一比较，直到找到合适的位置。此时有序区间是1、2、3、4、5、6，此时无序区间有空。</p></li><li><p>当无序区间为空，也就意味着排序结束。最终排序结果为：1、2、3、4、5、6。</p></li></ol></blockquote><h3 id="代码实现-2"><a href="#代码实现-2" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">5</span>, <span class="number">2</span>, <span class="number">4</span>, <span class="number">6</span>, <span class="number">1</span>, <span class="number">3</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> i; j &gt; <span class="number">0</span>; j--) &#123;</span><br><span class="line">				<span class="keyword">if</span>(arr[j-<span class="number">1</span>] &gt; arr[j])&#123;</span><br><span class="line">					arr[j-<span class="number">1</span>] = arr[j-<span class="number">1</span>] ^ arr[j];</span><br><span class="line">					arr[j] = arr[j-<span class="number">1</span>] ^ arr[j];</span><br><span class="line">					arr[j-<span class="number">1</span>] = arr[j-<span class="number">1</span>] ^ arr[j];</span><br><span class="line">				&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">					<span class="keyword">break</span>;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><blockquote><p>以上插入排序的java代码实现，代码中的第二个for循环是重点，第二个for循环是只比较当前数据左边的值，如果比左边的值小则交换位置，否则位置不变。</p></blockquote><h3 id="插入排序小结"><a href="#插入排序小结" class="headerlink" title="插入排序小结"></a>插入排序小结</h3><blockquote><p>插入排序适合如下类型的数组:</p><ol><li>数组中的每一个元素距离其最终的位置都不远。比如{1,0,2,3,4,5}，这个数组中0最终位置 应该是第一个位置，0此时的位置距离第一个位置不远。</li><li>一个有序的大数组中融入一个小数组。比如有序大数组{1,2,3,4,5,6}，融入一个小数组 {0,1}。</li><li>数组中只有几个元素的位置不正确。 上述这三种情况的数组适合使用插入排序算法。打过麻将的同学可以想想，打麻将过程中不停地摸牌、打牌、整理牌的过程是不是就是一次插入排序呢! 排序是算法的基础，排序的用途很多。</li></ol></blockquote><h2 id="快速排序"><a href="#快速排序" class="headerlink" title="快速排序"></a>快速排序</h2><h3 id="概念-3"><a href="#概念-3" class="headerlink" title="概念"></a>概念</h3><blockquote><p>快速排序（Quick Sort）是对冒泡排序的一种改进。由霍尔（C. A. R. Hoare）在1962年提出。</p><p>同冒泡排序一样，快速排序也属于交换排序算法，通过元素之间的比较和交换位置来达到排序的目的。</p></blockquote><h3 id="原理-3"><a href="#原理-3" class="headerlink" title="原理"></a>原理</h3><blockquote><p>通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。</p><p>快速排序与冒泡排序不同的是，冒泡排序在每一轮中只把1个元素冒泡到数列的一端。而快速排序每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就得到提升。</p><p>快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。这样总的比较和交换次数就少了，速度自然就提高了。</p><p>快速排序在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(n²)，它的平均时间复杂度为O(nlogn)。</p><p>快速排序这种思路就就是分治法。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/快速排序1.png" alt="image-20220731223128903" style="zoom:70%"><h3 id="步骤"><a href="#步骤" class="headerlink" title="步骤"></a>步骤</h3><blockquote><p>快速排序一般基于递归实现。其步骤是这样的：</p><ol><li><p>选定一个合适的值（理想情况中值最好，但实现中一般使用数组第一个值），称为“基准元素”(pivot)。</p></li><li><p>基于基准元素，将数组分为两部分，较小的分在左边，较大的分在右边。</p></li><li><p>第一轮下来，这个基准元素的位置一定在最终位置上。</p></li><li><p>对两个子数组分别重复上述过程，直到每个数组只有一个元素。</p></li><li><p>排序完成。</p></li></ol><p>总结：快速排序，其实就是给基准元素找其正确索引位置的过程。</p><p>注意：快速排序算法有双边循环法和单边循环法</p></blockquote><h4 id="A-双边循环法"><a href="#A-双边循环法" class="headerlink" title="A.双边循环法"></a>A.双边循环法</h4><blockquote><ol><li>首先，选定基准元素pivot，并且设置两个指针left和right，指向数列的最左和最右两个元素。</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731224403891.png" alt="image-20220731224403891" style="zoom:80%"><blockquote><p>从right指针开始，让指针所指向的元素和基准元素做比较。</p><p>right指向的数据如果小于pivot，则right指针停止移动，切换到left指针。否则right指针向左移动。</p><p>轮到left指针行动，让指针所指向的元素和基准元素做比较。</p><p>left指向的数据如果大于pivot，则left指针停止移动。否则left指针继续向右移动。</p><p>左右指针指向的元素交换位置。</p><p>right指针当前指向的数据1小于pivot，right指针停止，轮到left指针移动。</p><p>由于left开始指向的是基准元素，所以left右移1位。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731224525073.png" alt="image-20220731224525073" style="zoom:80%"><blockquote><p>left右移一位是7，由于7&gt;4，所以left指针停下。这时left和right指针所指向的元素进行交换。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731224607806.png" alt="image-20220731224607806" style="zoom:80%"><blockquote><ol start="2"><li>接下来重新切换到right指针，向左移动。right指针先移动到8，8&gt;4，继续左移，指向到2。由于2&lt;4，停止在2的位置。</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731224653449.png" alt="image-20220731224653449" style="zoom:70%"><blockquote><p>第一轮下来数组为：3、1、2、4、5、6、8、7。本轮下来，本轮的基准元素4的位置就是最终排序完成应该放置的位置。</p><p>接下来，采用递归的方式分别对4之前的前半部分排序，再对4后面的后半部分排序。</p></blockquote><h4 id="代码实现-3"><a href="#代码实现-3" class="headerlink" title="代码实现"></a>代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">	</span><br><span class="line">		<span class="type">int</span>[] arr = <span class="keyword">new</span> <span class="title class_">int</span>[]&#123;<span class="number">4</span>, <span class="number">7</span>, <span class="number">6</span>, <span class="number">5</span>, <span class="number">3</span>, <span class="number">2</span>, <span class="number">8</span>, <span class="number">1</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		quickSort(arr, <span class="number">0</span>, arr.length-<span class="number">1</span>);</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">quickSort</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> startIndex, <span class="type">int</span> endIndex)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span>(startIndex &gt;= endIndex)&#123;</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">pivotIndex</span> <span class="operator">=</span> partition(arr, startIndex, endIndex);</span><br><span class="line">	</span><br><span class="line">		<span class="comment">// 根据基准元素，分成两部分进行递归排序</span></span><br><span class="line">		quickSort(arr, startIndex, pivotIndex-<span class="number">1</span>);</span><br><span class="line">		quickSort(arr, pivotIndex+<span class="number">1</span>, endIndex);</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">partition</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> startIndex, <span class="type">int</span> endIndex)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 取第1个位置(也可以选择随机位置)的元素作为基准元素</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">pivot</span> <span class="operator">=</span> arr[startIndex];</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">left</span> <span class="operator">=</span> startIndex;</span><br><span class="line">		<span class="type">int</span> <span class="variable">right</span> <span class="operator">=</span> endIndex;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">while</span>(left != right)&#123;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">//控制right指针比较并左移</span></span><br><span class="line">			<span class="keyword">while</span>(left &lt; right &amp;&amp; arr[right] &gt; pivot)&#123;</span><br><span class="line">				right--;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="comment">//控制left指针比较并右移</span></span><br><span class="line">			<span class="keyword">while</span> (left &lt; right &amp;&amp; arr[left] &lt;= pivot) &#123;</span><br><span class="line">				left++;</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="comment">//交换left和right指针所指向的元素</span></span><br><span class="line">			<span class="keyword">if</span>(left &lt; right)&#123;</span><br><span class="line">				<span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> arr[left];</span><br><span class="line">				arr[left] = arr[right];</span><br><span class="line">				arr[right] = temp;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//交换left和right指针所指向的元素</span></span><br><span class="line">		arr[startIndex] = arr[left];</span><br><span class="line">		arr[left] = pivot;</span><br><span class="line">		<span class="keyword">return</span> left;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h4 id="B-单边循环法"><a href="#B-单边循环法" class="headerlink" title="B.单边循环法"></a>B.单边循环法</h4><blockquote><p>单边循环法只从数组的一边对元素进行遍历和交换。</p><ol><li>开始和双边循环法相似，首先选定基准元素pivot。同时，设置一个mark指针指向数列起始位置， 这个mark指针代表小于基准元素的区域边界。</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731232248321.png" alt="image-20220731232248321" style="zoom:80%"><blockquote><p>接下来，从基准元素的下一个位置开始遍历数组。</p><p>如果遍历到的元素大于基准元素，就继续往后遍历</p><p>如果遍历到的元素小于基准元素，则需要做两件事:</p><p>第一，把mark指针右移1位，因为小于pivot的区域边界增大了1;</p><p>第二，让最新遍历到的元素和mark指针所在位置的元素交换位置，因为最新遍历的元素归属于小 于pivot的区域</p><p>首先遍历到元素7，7&gt;4，所以继续遍历。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731232335033.png" alt="image-20220731232335033" style="zoom:80%"><blockquote><p>接下来遍历到的元素是3，3&lt;4，所以mark指针右移1位。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731232356401.png" alt="image-20220731232356401" style="zoom:80%"><blockquote><p>随后，让元素3和mark指针所在位置的元素交换，因为元素3归属于小于pivot的区域。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731232414066.png" alt="image-20220731232414066" style="zoom:80%"><blockquote><p>按照这个思路，继续遍历，后续步骤如图所示：</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220731232440930.png" alt="image-20220731232440930" style="zoom:80%"><h4 id="代码实现-4"><a href="#代码实现-4" class="headerlink" title="代码实现"></a>代码实现</h4><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//快速排序之单边循环法</span></span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = <span class="keyword">new</span> <span class="title class_">int</span>[]&#123;<span class="number">4</span>, <span class="number">7</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">2</span>, <span class="number">8</span>, <span class="number">1</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		quickSort(arr, <span class="number">0</span>, arr.length-<span class="number">1</span>);</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">quickSort</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> startIndex, <span class="type">int</span> endIndex)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span>(startIndex &gt;= endIndex)&#123;</span><br><span class="line">			<span class="keyword">return</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">pivotIndex</span> <span class="operator">=</span> partition(arr, startIndex, endIndex);</span><br><span class="line">	</span><br><span class="line">		<span class="comment">// 根据基准元素，分成两部分进行递归排序</span></span><br><span class="line">		quickSort(arr, startIndex, pivotIndex-<span class="number">1</span>);</span><br><span class="line">		quickSort(arr, pivotIndex+<span class="number">1</span>, endIndex);</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span> <span class="title function_">partition</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> startIndex, <span class="type">int</span> endIndex)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 取第1个位置(也可以选择随机位置)的元素作为基准元素</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">pivot</span> <span class="operator">=</span> arr[startIndex];</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">mark</span> <span class="operator">=</span> startIndex;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> startIndex+<span class="number">1</span>; i &lt;= endIndex; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span>(pivot &gt; arr[i])&#123;</span><br><span class="line">				mark++;</span><br><span class="line">				<span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> arr[mark];</span><br><span class="line">				arr[mark] = arr[i];</span><br><span class="line">				arr[i] = temp;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">temp</span> <span class="operator">=</span> arr[startIndex];</span><br><span class="line">		arr[startIndex] = arr[mark];</span><br><span class="line">		arr[mark] = temp;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">return</span> mark;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="希尔排序"><a href="#希尔排序" class="headerlink" title="希尔排序"></a>希尔排序</h2><h3 id="概念-4"><a href="#概念-4" class="headerlink" title="概念"></a>概念</h3><blockquote><p>希尔排序(Shell’s Sort)是插入排序的一种，又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。</p><p>希尔排序是基于插入排序的以下两点性质而提出改进方法的：</p><p>插入排序本身还不够高效，插入排序每次只能将数据移动一位。当有大量数据需要排序时，会需要大量的移位操作。</p><p>但是插入排序在对几乎已经排好序的数据操作时，效率很高，几乎可以达到线性排序的效率。</p><p>所以，如果能对数据进行初步排列后，再用插入排序，那么就会大大提高效率。</p><p>希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；当增量减至 1 时，整个文件恰被分成一组，算法便终止。</p><p>由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。</p></blockquote><h3 id="原理-4"><a href="#原理-4" class="headerlink" title="原理"></a>原理</h3><blockquote><p>把元素按步长gap分组，对每组元素采用直接插入排序方法进行排序；</p><p>随着步长逐渐减小，所分成的组包含的元素越来越多；</p><p>当步长值减小到1时，整个数据合成一组，构成一组有序记录，完成排序；</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220801010017817.png" alt="image-20220801010017817" style="zoom:70%"><h3 id="代码实现-5"><a href="#代码实现-5" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = <span class="keyword">new</span> <span class="title class_">int</span>[]&#123;<span class="number">9</span>, <span class="number">1</span>, <span class="number">2</span>, <span class="number">5</span>, <span class="number">7</span>, <span class="number">4</span>, <span class="number">8</span>, <span class="number">6</span>, <span class="number">3</span>, <span class="number">5</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">gap</span> <span class="operator">=</span> arr.length/<span class="number">2</span>; gap &gt; <span class="number">0</span>; gap/=<span class="number">2</span>) &#123;</span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> gap; i &lt; arr.length; i++) &#123;</span><br><span class="line">				<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> i-gap; j &gt;= <span class="number">0</span>; j-= gap) &#123;</span><br><span class="line">					System.out.println(j + <span class="string">&quot; -- &quot;</span> + (j+gap));</span><br><span class="line">					<span class="keyword">if</span>(arr[j] &gt; arr[j+gap])&#123;</span><br><span class="line">						arr[j] = arr[j]^arr[j+gap];</span><br><span class="line">						arr[j+gap] = arr[j]^arr[j+gap];</span><br><span class="line">						arr[j] = arr[j]^arr[j+gap];</span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">				System.out.println(<span class="string">&quot;xxxxx&quot;</span>);</span><br><span class="line">			&#125;</span><br><span class="line">			System.out.println(<span class="string">&quot;yyyy&quot;</span>);</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h3 id="希尔排序优劣"><a href="#希尔排序优劣" class="headerlink" title="希尔排序优劣"></a>希尔排序优劣</h3><blockquote><p>优点：算法较简单，代码短，需要的空间小，速度还可以，适合中小规模的排序。<br>缺点：速度偏慢，不够智能，不适合情况简单的排序，不适合大规模排序。</p></blockquote><h3 id="希尔排序稳定性"><a href="#希尔排序稳定性" class="headerlink" title="希尔排序稳定性"></a>希尔排序稳定性</h3><blockquote><p>希尔排序是不稳定的算法，它满足稳定算法的定义。对于相同的两个数，可能由于分在不同的组中而导致它们的顺序发生变化。</p><p>算法稳定性 – 假设在数列中存在a[i]&#x3D;a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！</p></blockquote><h2 id="归并排序"><a href="#归并排序" class="headerlink" title="归并排序"></a>归并排序</h2><h3 id="概念-5"><a href="#概念-5" class="headerlink" title="概念"></a>概念</h3><blockquote><p>归并排序是一类与插入排序、交换排序、选择排序不同的另一种排序方法。</p><p>归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。</p><p>将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。</p><p>归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。</p></blockquote><h3 id="原理-5"><a href="#原理-5" class="headerlink" title="原理"></a>原理</h3><blockquote><p>分而治之(divide - conquer)。</p><p>每个递归过程涉及三个步骤：</p><p>第一, 分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n&#x2F;2 个元素；</p><p>第二, 治理: 对每个子序列分别调用归并排序MergeSort，进行递归操作；</p><p>第三, 合并: 合并两个排好序的子序列，生成排序结果。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220801015153838.png" alt="image-20220801015153838" style="zoom:70%"><blockquote><p>归并排序图片演示</p><p><a target="_blank" rel="noopener" href="https://img-blog.csdn.net/20180607002713740">https://img-blog.csdn.net/20180607002713740</a></p></blockquote><h3 id="代码实现-6"><a href="#代码实现-6" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line"></span><br><span class="line">		<span class="type">int</span>[] arr = <span class="keyword">new</span> <span class="title class_">int</span>[]&#123;<span class="number">4</span>, <span class="number">7</span>, <span class="number">3</span>, <span class="number">5</span>, <span class="number">6</span>, <span class="number">2</span>, <span class="number">8</span>, <span class="number">1</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		mergeSort(arr, <span class="number">0</span>, arr.length-<span class="number">1</span>);</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">mergeSort</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> low, <span class="type">int</span> high)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">if</span>(low &lt; high)&#123;</span><br><span class="line">			</span><br><span class="line">			<span class="type">int</span> <span class="variable">mid</span> <span class="operator">=</span> (low+high)/<span class="number">2</span>;</span><br><span class="line">			</span><br><span class="line">			mergeSort(arr, low, mid);</span><br><span class="line">			mergeSort(arr, mid+<span class="number">1</span>, high);</span><br><span class="line">			<span class="comment">// 左右归并</span></span><br><span class="line">			merge(arr, low, mid, high);</span><br><span class="line">			</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">merge</span><span class="params">(<span class="type">int</span>[] arr, <span class="type">int</span> low, <span class="type">int</span> mid, <span class="type">int</span> high)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] temp = <span class="keyword">new</span> <span class="title class_">int</span>[high-low+<span class="number">1</span>];</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> low;</span><br><span class="line">		<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> mid+<span class="number">1</span>;</span><br><span class="line">		<span class="type">int</span> <span class="variable">k</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 把较小的数先移到新数组中</span></span><br><span class="line">		<span class="keyword">while</span>(i&lt;=mid &amp;&amp; j&lt;=high)&#123;</span><br><span class="line">			<span class="keyword">if</span>(arr[i]&lt;arr[j])&#123;</span><br><span class="line">				temp[k++] = arr[i++];</span><br><span class="line">			&#125;<span class="keyword">else</span>&#123;</span><br><span class="line">				temp[k++] = arr[j++];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 把左边剩余的数移入数组</span></span><br><span class="line">		<span class="keyword">while</span>(i &lt;= mid)&#123;</span><br><span class="line">			temp[k++] = arr[i++];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 把右边边剩余的数移入数组</span></span><br><span class="line">		<span class="keyword">while</span>(j &lt;= high)&#123;</span><br><span class="line">			temp[k++] = arr[j++];</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">// 把新数组中的元素覆盖arr数组</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">x</span> <span class="operator">=</span> <span class="number">0</span>; x &lt; temp.length; x++) &#123;</span><br><span class="line">			arr[x+low] = temp[x];</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="桶排序"><a href="#桶排序" class="headerlink" title="桶排序"></a>桶排序</h2><h3 id="概念-6"><a href="#概念-6" class="headerlink" title="概念"></a>概念</h3><blockquote><p>桶排序，顾名思义会用到“桶” 。核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。</p><p>桶排序同样是一种线性时间的排序算法。桶排序需要创建若干个桶来协助排序，每一个桶(bucket)代表一个区间范围，里面可以承载一个或多个元素。</p><p>除了对一个桶内的元素做链表存储，也有可能对每个桶中的元素继续使用其他排序算法进行排序，所以更多时候，桶排序会结合其他排序算法一起使用。</p><p>桶排序对排序的数据要求苛刻：</p><ol><li>要排序的数据需要很容易就能划分成m个桶，并且桶与桶之间有着天然的大小顺序；</li><li>数据在各个桶之间的分布是比较均匀的；</li><li>桶排序比较适合用在外部排序中。</li></ol><p>所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。</p></blockquote><h3 id="原理-6"><a href="#原理-6" class="headerlink" title="原理"></a>原理</h3><blockquote><ol><li>桶排序的第1步，就是创建这些桶，并确定每一个桶的区间范围具体需要建立多少个桶，如何确定桶的区间范围，有很多种不同的方式。我们这里创建的桶数量等于原始数列的元素数量，除最后一个桶只包含数列最大值外， 前面各个桶的区间按照比例来确定。</li></ol><p>区间跨度 &#x3D; (最大值-最小值)&#x2F; (桶的数量 - 1)</p><p>假设有一个非整数数列如下：<strong>4.5、0.84、3.25、2.18、0.5</strong></p><p>桶的个数为5，计算出区间跨度为1。</p><p>序列：4.5、0.84、3.25、2.18、0.5</p><p>区间跨度 &#x3D; (最大值-最小值)&#x2F;(桶的数量-1)</p><p>区间跨度 &#x3D; 1.0</p><p>0.5-1.5 （0号桶中：0.84, 0.5）</p><p>1.5-2.5 （1号桶中：2.18）</p><p>2.5-3.5 （2号桶中：3.25）</p><p>3.5-4.5 （3号桶中：空）</p><p>4.5-5.5 （4号桶中：4.5）</p><p>如何计算当前数据属于某个区间，或者说在哪个桶里？</p><p>桶编号 &#x3D; (int) ((元素数值 - 最小值) &#x2F; 区间跨度);</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220802201909454.png" alt="image-20220802201909454" style="zoom:67%"><blockquote><ol start="2"><li>遍历原始数列，把元素对号入座放入各个桶中。</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220802201939921.png" alt="image-20220802201939921" style="zoom:67%"><blockquote><ol start="3"><li>对每个桶内部的元素分别进行排序(显然，只有第1个桶需要排序)</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220802201959409.png" alt="image-20220802201959409" style="zoom:67%"><blockquote><ol start="4"><li>遍历所有的桶，输出所有元素 ：0.5、0.84、2.18、3.25、4.5</li></ol></blockquote><h3 id="代码实现-7"><a href="#代码实现-7" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//桶排序</span></span><br><span class="line">		</span><br><span class="line">		<span class="type">double</span>[] arr = <span class="keyword">new</span> <span class="title class_">double</span>[]&#123;<span class="number">4.5</span>, <span class="number">0.84</span>, <span class="number">3.25</span>, <span class="number">2.18</span>, <span class="number">0.5</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		bucketSort(arr);</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line"></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">bucketSort</span><span class="params">(<span class="type">double</span>[] arr)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 获取最大值和最小值</span></span><br><span class="line">		<span class="type">double</span> <span class="variable">max</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line">		<span class="type">double</span> <span class="variable">min</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">1</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span>(max &lt; arr[i])&#123;</span><br><span class="line">				max = arr[i];</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span>(min &gt; arr[i])&#123;</span><br><span class="line">				min = arr[i];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 获取桶个数</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">bucketCount</span> <span class="operator">=</span> arr.length;</span><br><span class="line">		<span class="comment">// 计算区间跨度 = (最大值-最小值)/(桶的数量-1)</span></span><br><span class="line">		<span class="type">double</span> <span class="variable">span</span> <span class="operator">=</span> (max-min)/(bucketCount-<span class="number">1</span>);</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 桶的初始化</span></span><br><span class="line">		ArrayList&lt;LinkedList&lt;Double&gt;&gt; list = <span class="keyword">new</span> <span class="title class_">ArrayList</span>&lt;&gt;(bucketCount);</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; bucketCount; i++) &#123;</span><br><span class="line">			list.add(<span class="keyword">new</span> <span class="title class_">LinkedList</span>&lt;&gt;());</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 循环获取元素应该放在哪个区间内，也就是获取桶的编号</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">// 获取当前数据应该放在哪个区间内，也就是获取桶的编号</span></span><br><span class="line">			<span class="type">int</span> <span class="variable">num</span> <span class="operator">=</span> (<span class="type">int</span>) ((arr[i]-min)/span);</span><br><span class="line">			list.get(num).add(arr[i]);</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 对每个桶内部进行排序</span></span><br><span class="line">		<span class="keyword">for</span> (LinkedList&lt;Double&gt; linkedList : list) &#123;</span><br><span class="line">			Collections.sort(linkedList);</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 将数据回填到原数组中</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (LinkedList&lt;Double&gt; linkedList : list) &#123;</span><br><span class="line">			<span class="keyword">for</span> (Double element : linkedList) &#123;</span><br><span class="line">				arr[index++] = element;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="基数排序"><a href="#基数排序" class="headerlink" title="基数排序"></a>基数排序</h2><h3 id="概念-7"><a href="#概念-7" class="headerlink" title="概念"></a>概念</h3><blockquote><p>基数排序是桶排序的扩展。是1887年赫尔曼.何乐礼发明的。基数排序的基本实现原理是：将整数按位切割成不同的数字，然后按位数进行比较。</p><p>基数排序是经典的空间换时间的算法。占用内存很大，当对海量数据排序时，容易造成OutOfMemoryError。</p></blockquote><h3 id="原理-7"><a href="#原理-7" class="headerlink" title="原理"></a>原理</h3><blockquote><ol><li><p>有一串数值如下所示：64, 32, 90,76, 11,93, 85, 44, 18, 21, 65, 89, 57,11</p><p>首先根据个位数的数值，将它们分配至编号0到9的桶子中：</p></li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220808104847943.png" alt="image-20220808104847943" style="zoom:87%"><blockquote><ol start="2"><li><p>将这些桶子中的数值重新串接起来，成为的数列为：90, 11, 21, 11, 32, 93, 64, 44, 85, 65, 76, 57, 18, 89</p><p>接着再进行一次分配，这次是根据十位数来分配：</p></li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220808104926030.png" alt="image-20220808104926030" style="zoom:80%"><blockquote><ol start="3"><li><p>将这些桶子中的数值重新串接起来，成为的数列为：11, 11, 18, 21, 32, 44, 57, 64, 65, 76, 85, 89, 90, 93</p><p>这时候整个数列已经排序完毕。</p><p>如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。</p></li></ol></blockquote><h3 id="代码实现-8"><a href="#代码实现-8" class="headerlink" title="代码实现"></a>代码实现</h3><blockquote><p>基数排序的实现，有两种方式。</p><p>低位优先法，适用于位数较小的数排序，简称LSD。</p><p>高位优先法，适用于位数较多的情况，简称MSD。</p><p>LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。</p><p>MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。</p></blockquote><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		<span class="comment">//基数排序</span></span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">64</span>, <span class="number">32</span>, <span class="number">90</span>,<span class="number">76</span>, <span class="number">11</span>,<span class="number">93</span>, <span class="number">85</span>, <span class="number">44</span>, <span class="number">18</span>, <span class="number">21</span>, <span class="number">65</span>, <span class="number">89</span>, <span class="number">57</span>, <span class="number">11</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		radixSort(arr);</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">radixSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//获取最大值</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">max</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">1</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span>(max &lt; arr[i])&#123;</span><br><span class="line">				max = arr[i];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//获取最大值的位数(目的：用来判断需要进行几轮基数排序)</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">maxLen</span> <span class="operator">=</span> String.valueOf(max).length();</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//定义10个桶容器。</span></span><br><span class="line">		<span class="comment">// 数组的第一维表示0-9，二维下标按照最大可能arr.length来计算。</span></span><br><span class="line">		<span class="type">int</span>[][] bucket = <span class="keyword">new</span> <span class="title class_">int</span>[<span class="number">10</span>][arr.length];</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//创建桶计数器</span></span><br><span class="line">		<span class="comment">// 记录每个桶中放置数据的个数。数组元素共10个，表示10个桶。</span></span><br><span class="line">		<span class="comment">// 数组索引表示桶的编号，索引对应的数值是该桶中的数据个数</span></span><br><span class="line">		<span class="type">int</span>[] elementCount = <span class="keyword">new</span> <span class="title class_">int</span>[<span class="number">10</span>];</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//times是记录重复操作轮数的计数器。重复次数取决了最大数值的位数</span></span><br><span class="line">		<span class="comment">//循环中定义变量n，用来表示位数。1表示个位，10表示十位，100表示百位。目的是获取数字每个位上的值。</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> times= <span class="number">1</span>, n = <span class="number">1</span>; times&lt;= maxLen; times++,n*=<span class="number">10</span>) &#123;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">// 遍历数值，放到桶中</span></span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">				</span><br><span class="line">				<span class="comment">//获取元素个位、十位、百位上的数字。就是桶编号</span></span><br><span class="line">				<span class="type">int</span> <span class="variable">lsd</span> <span class="operator">=</span> arr[i]/n%<span class="number">10</span>;</span><br><span class="line">				<span class="comment">//将数值放入桶中</span></span><br><span class="line">				bucket[lsd][elementCount[lsd]] = arr[i];</span><br><span class="line">				<span class="comment">//桶计数器增加</span></span><br><span class="line">				elementCount[lsd]++;</span><br><span class="line">			&#125;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">//数组索引下标。每轮结束都要形成新的数列，数组下标重新记录。</span></span><br><span class="line">			<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">			</span><br><span class="line">			<span class="comment">// 从10个桶中取出数据，形成新的数列</span></span><br><span class="line">			<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; bucket.length; i++) &#123;</span><br><span class="line">				</span><br><span class="line">				<span class="comment">//判断桶中是否有数据</span></span><br><span class="line">				<span class="keyword">if</span>(elementCount[i] &gt; <span class="number">0</span>)&#123;</span><br><span class="line">					</span><br><span class="line">					<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; elementCount[i]; j++) &#123;</span><br><span class="line">						arr[index++] = bucket[i][j]; </span><br><span class="line">					&#125;</span><br><span class="line">				&#125;</span><br><span class="line">				<span class="comment">//遍历完数据，将计数器清空，下次重新计数</span></span><br><span class="line">				elementCount[i] = <span class="number">0</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="计数排序"><a href="#计数排序" class="headerlink" title="计数排序"></a>计数排序</h2><h3 id="概念-8"><a href="#概念-8" class="headerlink" title="概念"></a>概念</h3><blockquote><p>计数排序，这种排序算法是利用数组下标来确定元素的正确位置的。</p><p>计数排序是基本的桶排序。</p><p>定义n个桶，每个桶一个编号，数据放到相应编号的桶中。定义一个数组，数组索引表示桶的编号，索引值就是存放的数值。如果该值为1说明只出现一次，如果大于1，说明重复多次出现。</p><p>计数排序是典型的空间换时间的算法。</p></blockquote><h3 id="原理-8"><a href="#原理-8" class="headerlink" title="原理"></a>原理</h3><blockquote><ol><li>假设数组中有10个整数，取值范围为0~10，要求用最快的速度把这10个整数从小到大进行排序。 可以根据这有限的范围，建立一个长度为10的数组。数组下标从0到9，元素初始值全为0。</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220803204530655.png" alt="image-20220803204530655" style="zoom:80%"><blockquote><p>假设数组数据为：7 3 2 1 9 6 5 4 3 8</p><p>下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，对应数组下标的元素进行加1操作。</p><p>最终，当数列遍历完毕时，数组的状态如下：</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220803204556612.png" alt="image-20220803204556612" style="zoom:80%"><blockquote><p>该数组中每一个下标位置所对应的值，其实就是数列中对应整数出现的次数。</p><p>直接遍历数组，输出数组元素的下标值，元素的值就是输出的次数。0不输出。</p><p>输出： 1 2 3 3 4 5 6 7 8 9</p></blockquote><blockquote><ol start="2"><li>如果起始数不是从0开始，比如以下数列：</li></ol><p>95，94，91，98，99，90，99，93，91，92，数组起始数为90。就采用偏移量的方式来排序。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220803204707963.png" alt="image-20220803204707963" style="zoom:80%"><blockquote><p>数组遍历完毕，数组的状态如下：</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220803204725252.png" alt="image-20220803204725252" style="zoom:80%"><blockquote><p>原本输出：0 1 1 2 3 4 5 8 9 9</p><p>增加上偏移量90后，实际应该顺序输出为：90 91 91 92 93 94 95 98 99 99</p></blockquote><h3 id="代码实现-9"><a href="#代码实现-9" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		<span class="comment">//计数排序</span></span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = makeRandomArr(<span class="number">50</span>, <span class="number">60</span>, <span class="number">100</span>);</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">		</span><br><span class="line">		countSort(arr);</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">countSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 获取最大值和最小值</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">max</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line">		<span class="type">int</span> <span class="variable">min</span> <span class="operator">=</span> arr[<span class="number">0</span>];</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span>(max &lt; arr[i])&#123;</span><br><span class="line">				max = arr[i];</span><br><span class="line">			&#125;</span><br><span class="line">			<span class="keyword">if</span>(min &gt; arr[i])&#123;</span><br><span class="line">				min = arr[i];</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 计算桶的数量</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">bucketNum</span> <span class="operator">=</span> max-min+<span class="number">1</span>;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//创建桶数组</span></span><br><span class="line">		<span class="type">int</span>[] buckets = <span class="keyword">new</span> <span class="title class_">int</span>[bucketNum];</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//遍历原数组</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			<span class="comment">//计算元素在桶中的编号</span></span><br><span class="line">			<span class="type">int</span> <span class="variable">n</span> <span class="operator">=</span> arr[i]-min;</span><br><span class="line">			<span class="comment">//桶上计数累加</span></span><br><span class="line">			++buckets[n];</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">// 将数据回填到原数组中</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">index</span> <span class="operator">=</span> <span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; buckets.length; i++) &#123;</span><br><span class="line">			<span class="keyword">if</span>(buckets[i] &gt; <span class="number">0</span>)&#123;</span><br><span class="line">				<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">j</span> <span class="operator">=</span> <span class="number">0</span>; j &lt; buckets[i]; j++) &#123;</span><br><span class="line">					<span class="comment">// 实际数值 = 桶编号 + 最小数值</span></span><br><span class="line">					arr[index++] = i + min;</span><br><span class="line">				&#125;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 全班50个人，最低成绩60分，最高成绩100分。将这些成绩进行排序。</span></span><br><span class="line"><span class="comment">     * 随机生成50个成绩。</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="type">int</span>[] makeRandomArr(<span class="type">int</span> count,<span class="type">int</span> min,<span class="type">int</span> max)&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = <span class="keyword">new</span> <span class="title class_">int</span>[count];</span><br><span class="line">		</span><br><span class="line">		<span class="type">Random</span> <span class="variable">ran</span> <span class="operator">=</span> <span class="keyword">new</span> <span class="title class_">Random</span>();</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> <span class="number">0</span>; i &lt; arr.length; i++) &#123;</span><br><span class="line">			<span class="type">int</span> <span class="variable">element</span> <span class="operator">=</span> ran.nextInt(max-min)+min;</span><br><span class="line">			arr[i] = element;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">return</span> arr;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="堆排序"><a href="#堆排序" class="headerlink" title="堆排序"></a>堆排序</h2><h3 id="概念-9"><a href="#概念-9" class="headerlink" title="概念"></a>概念</h3><blockquote><p>堆是具有以下性质的完全二叉树</p><p>大顶堆：每个节点的值都大于或等于其左右孩子节点的值<strong>。</strong></p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220808162453505.png" alt="image-20220808162453505" style="zoom:87%"><blockquote><p>小顶堆：每个结点的值都小于或等于其左右孩子结点的值。</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220808162513989.png" alt="image-20220808162513989" style="zoom:80%"><blockquote><p>对堆中的结点按层进行编号，将这种逻辑结构映射到数组中：</p></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/image-20220808162534054.png" alt="image-20220808162534054" style="zoom:80%"><blockquote><p>该数组从逻辑上讲就是一个堆结构，用简单的公式来描述一下堆的定义就是:</p><p>大顶堆:arr[i] &gt;&#x3D; arr[2i+1] &amp;&amp; arr[i] &gt;&#x3D; arr[2i+2]</p><p>小顶堆:arr[i] &lt;&#x3D; arr[2i+1] &amp;&amp; arr[i] &lt;&#x3D; arr[2i+2]</p></blockquote><h3 id="原理-9"><a href="#原理-9" class="headerlink" title="原理"></a>原理</h3><blockquote><p>将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。 将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得 到n个元素的次小值。如此反复执行，便能得到一个有序序列了。</p></blockquote><blockquote><ol><li><p>构造初始堆</p><p>将给定无序序列构造成一个大顶堆(一般升序采用大顶堆，降序采用小顶堆)。</p></li></ol></blockquote><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps1.jpg" alt="img"></p><blockquote><ol start="2"><li>此时从最后一个非叶子节点开始(叶子节点自然不用调整，第一个非叶子节点 arr.length&#x2F;2- 1&#x3D;5&#x2F;2-1&#x3D;1，也就是下面的6结点)，从左至右，从下至上进行调整。</li></ol></blockquote><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps2.jpg" alt="img"></p><blockquote><ol start="3"><li>找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换</li></ol></blockquote><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps3.jpg" alt="img"></p><blockquote><ol start="4"><li>这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。</li></ol></blockquote><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps4.jpg" alt="img"></p><blockquote><p>此时，我们就将一个无序序列构造成了一个大顶堆。</p></blockquote><blockquote><ol start="5"><li>将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。将堆顶元素9和末尾元素4进行交换</li></ol></blockquote><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps5.jpg" alt="img"></p><blockquote><p>重新调整结构，使其继续满足大顶堆</p></blockquote><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps6.jpg" alt="img"></p><blockquote><p>再将堆顶元素8与末尾元素5进行交换，得到第二大元素8</p></blockquote><p><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps7.jpg" alt="img"></p><blockquote><p>继续进行调整成大顶堆，顶部的6与右子树的4交换，最终使得整个序列有序。</p></blockquote><h3 id="代码实现-10"><a href="#代码实现-10" class="headerlink" title="代码实现"></a>代码实现</h3><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">public</span> <span class="keyword">class</span> <span class="title class_">Test01</span> &#123;</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">main</span><span class="params">(String[] args)</span> &#123;</span><br><span class="line">		<span class="comment">//堆排序</span></span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span>[] arr = &#123;<span class="number">4</span>, <span class="number">6</span>, <span class="number">8</span>, <span class="number">5</span>, <span class="number">9</span>&#125;;</span><br><span class="line">		</span><br><span class="line">		heapSort(arr);</span><br><span class="line">		</span><br><span class="line">		System.out.println(Arrays.toString(arr));</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">heapSort</span><span class="params">(<span class="type">int</span>[] arr)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="comment">//构建堆</span></span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> arr.length/<span class="number">2</span>-<span class="number">1</span>; i &gt;= <span class="number">0</span>; i--) &#123;</span><br><span class="line">			adjustHeap(arr, i, arr.length);</span><br><span class="line">		&#125;</span><br><span class="line">		</span><br><span class="line">		<span class="keyword">for</span> (<span class="type">int</span> <span class="variable">i</span> <span class="operator">=</span> arr.length-<span class="number">1</span>; i &gt; <span class="number">0</span>; i--) &#123;</span><br><span class="line">			<span class="comment">//堆顶与末尾元素调换</span></span><br><span class="line">			arr[<span class="number">0</span>] = arr[<span class="number">0</span>]^arr[i];</span><br><span class="line">			arr[i] = arr[<span class="number">0</span>]^arr[i];</span><br><span class="line">			arr[<span class="number">0</span>] = arr[<span class="number">0</span>]^arr[i];</span><br><span class="line">			</span><br><span class="line">			<span class="comment">//将堆顶元素下沉（目的：是将最大元素上浮到堆顶）</span></span><br><span class="line">			adjustHeap(arr, <span class="number">0</span>, i);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	</span><br><span class="line">	<span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title function_">adjustHeap</span><span class="params">(<span class="type">int</span>[] arr,<span class="type">int</span> index,<span class="type">int</span> length)</span>&#123;</span><br><span class="line">		</span><br><span class="line">		<span class="type">int</span> <span class="variable">leftChild</span> <span class="operator">=</span> index+<span class="number">1</span>;<span class="comment">//左边节点下标</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">rightChild</span> <span class="operator">=</span> index+<span class="number">2</span>;<span class="comment">//右边节点下标</span></span><br><span class="line">		<span class="type">int</span> <span class="variable">parentIndex</span> <span class="operator">=</span> index;<span class="comment">//父节点下标</span></span><br><span class="line">		</span><br><span class="line">		<span class="comment">//下沉左边</span></span><br><span class="line">		<span class="keyword">if</span>(leftChild &lt; length &amp;&amp; arr[parentIndex] &lt; arr[leftChild])&#123;</span><br><span class="line">			parentIndex = leftChild;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="comment">//下沉右边</span></span><br><span class="line">		<span class="keyword">if</span>(rightChild &lt; length &amp;&amp; arr[parentIndex] &lt; arr[rightChild])&#123;</span><br><span class="line">			parentIndex = rightChild;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">if</span>(index != parentIndex)&#123;</span><br><span class="line">			</span><br><span class="line">			arr[index] = arr[index] ^ arr[parentIndex];</span><br><span class="line">			arr[parentIndex] = arr[index] ^ arr[parentIndex];</span><br><span class="line">			arr[index] = arr[index] ^ arr[parentIndex];</span><br><span class="line">			</span><br><span class="line">			<span class="comment">//继续下沉</span></span><br><span class="line">			adjustHeap(arr, parentIndex, length);</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure><h2 id="Arrays-sort"><a href="#Arrays-sort" class="headerlink" title="Arrays.sort()"></a>Arrays.sort()</h2><h3 id="概念-10"><a href="#概念-10" class="headerlink" title="概念"></a>概念</h3><blockquote><p>Arrays.sort排序算法是双基准元素快速排序DualPivotQuicksort。</p><p>由弗拉基米尔·雅罗斯拉夫斯基Vladimir Yaroslavskiy，乔恩·本特利Jon Bentley和约书亚·布洛克Josh Bloch提供该算法。</p><p>在许多数据集上表现出O(nlogn)的时间复杂度，比传统的(单基准元素)快速排序算法性能更快。</p></blockquote><h3 id="原理-10"><a href="#原理-10" class="headerlink" title="原理"></a>原理</h3><blockquote><ol><li><p>在微小数组上使用插入排序（Use insertion sort on tiny arrays）</p><p>int INSERTION_SORT_THRESHOLD &#x3D; 47;</p><p>如果要排序的数组长度小于INSERTION_SORT_THRESHOLD这个常量，则插入排序优先于快速排序。</p></li></ol></blockquote><blockquote><ol start="2"><li><p>对小数组使用快速排序（Use Quicksort on small arrays）</p><p>int QUICKSORT_THRESHOLD &#x3D; 286;</p><p>如果要排序的数组长度小于QUICKSORT_THRESHOLD这个常量，则快速排序优先于归并排序。</p></li></ol></blockquote><blockquote><ol start="3"><li><p>数组接近排序，使用归并排序（Check if the array is nearly sorted）</p><p>int MAX_RUN_COUNT &#x3D; 67; &#x2F;&#x2F;归并排序的最大运行次数。</p><p>int MAX_RUN_LENGTH &#x3D; 33; &#x2F;&#x2F;归并排序运行的最大长度。</p><p>数组不是高度结构化的，使用快速排序代替归并排序。</p></li></ol></blockquote><blockquote><ol start="4"><li><p>对大数组使用计数排序（Use counting sort on large arrays）</p><p>int COUNTING_SORT_THRESHOLD_FOR_BYTE &#x3D; 29;</p><p>如果要排序的字节数组的长度大于COUNTING_SORT_THRESHOLD_FOR_BYTE该常量，则优先使用计数排序而不是插入排序。</p></li></ol></blockquote><blockquote><ol start="5"><li><p>对大数组使用计数排序（Use counting sort on large arrays）</p><p>int COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR &#x3D; 3200;</p><p>如果要排序的短数组或char数组的长度大于COUNTING_SORT_THRESHOLD_FOR_SHORT_OR_CHAR该常量，则优先使用计数排序而不是快速排序。</p></li></ol></blockquote><h3 id="源码截图"><a href="#源码截图" class="headerlink" title="源码截图"></a>源码截图</h3><blockquote><ol><li>在微小数组上使用插入排序（Use insertion sort on tiny arrays）</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps8.jpg" alt="img" style="zoom:80%"><blockquote><ol start="2"><li>对小数组使用快速排序（Use Quicksort on small arrays）</li></ol></blockquote><img src="/wps9.jpg" alt="img" style="zoom:80%"><blockquote><ol start="3"><li>数组接近排序，使用归并排序（Check if the array is nearly sorted）</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps10.jpg" alt="img" style="zoom:80%"><blockquote><ol start="4"><li>对大数组使用计数排序（Use counting sort on large arrays）</li></ol></blockquote><img src="/wps11.jpg" alt="img" style="zoom:80%"><blockquote><ol start="5"><li>对大数组使用计数排序（Use counting sort on large arrays）</li></ol></blockquote><img src="https://image.insectmk.cn/hexo-gitee-blog/article/_post/education/qianfeng/day09-3/wps12.jpg" alt="img" style="zoom:80%"><h2 id="排序算法与复杂度归类"><a href="#排序算法与复杂度归类" class="headerlink" title="排序算法与复杂度归类"></a>排序算法与复杂度归类</h2><blockquote><p>注：学习完<strong>时间复杂度和空间复杂度</strong>的内容再做一下学习</p><ol><li><p>根据时间复杂度的不同，主流的排序算法可以分为3大类：</p><p>时间复杂度为O(n²)的排序算法：冒泡排序、选择排序、插入排序（冒选插）</p><p>时间复杂度为O(nlogn)的排序算法： 快速排序 、堆排序、希尔排序、归并排序 （快堆希归）</p><p>时间复杂度为线性O(n)的排序算法：桶排序、 计数排序、基数排序（桶计基）</p></li></ol><p>各个排序算法比对表:</p></blockquote><table><thead><tr><th><strong>排序算法</strong></th><th><strong>时间复杂度</strong></th><th><strong>空间复杂度</strong></th><th><strong>是否稳定</strong></th><th>比较次数</th></tr></thead><tbody><tr><td>冒泡排序</td><td>平均、最差：O(n²)</td><td>O(1)</td><td>稳定</td><td>未优化无序&#x2F;有序：(n-1)² 优化有序：n-1 优化最差：n(n-1)&#x2F;2</td></tr><tr><td>选择排序</td><td>平均、最差：O(n²)</td><td>O(1)</td><td>不稳定</td><td>无序&#x2F;有序固定：n(n-1)&#x2F;2</td></tr><tr><td>插入排序</td><td>平均、最差：O(n²)</td><td>O(1)</td><td>稳定</td><td>有序：n-1 无序最差：n(n-1)&#x2F;2</td></tr><tr><td>快速排序</td><td>平均、最差：O(nlogn)</td><td>O(nlogn)</td><td>不稳定</td><td>属于交换排序</td></tr><tr><td>堆排序</td><td>平均、最差：O(nlogn)</td><td>O(1)</td><td>不稳定</td><td>属于选择排序</td></tr><tr><td>希尔排序</td><td>平均：O(n^1.5) 最好：O(nlogn)</td><td>O(1)</td><td>不稳定</td><td>(n-1)^1.5 nlogn</td></tr><tr><td>归并排序</td><td>平均、最差：O(nlogn)</td><td>O(n)</td><td>稳定</td><td></td></tr><tr><td>桶排序</td><td>O(n)</td><td>O(n)</td><td>稳定</td><td>适用于浮点数，适用于外部排序</td></tr><tr><td>计数排序</td><td>O(m+n)</td><td>O(m) 0-10 m&#x3D;10？</td><td>稳定</td><td>适合于连续的取值范围不大的数组</td></tr><tr><td>基数排序</td><td>平均、最差：O(d*n) d为位数</td><td>O(n)</td><td>稳定</td><td>处理海量数据排序时容易OutOfMemoryError</td></tr></tbody></table><blockquote><ol start="2"><li><p>各种排序算法性能对比</p><p>执行1万个随机数的排序，同一台机器相同条件下的测试结果：</p><p>冒泡145ms、选择95ms、插入46ms</p><p>快速2ms、堆2ms、希尔5ms、归并3ms</p><p>计数1ms、基数2ms、桶17ms</p><p>Arrays.sort:4ms</p><p>Collections.sort:10ms</p><p>执行5万个随机数的排序，同一台机器相同条件下的测试结果：</p><p>冒泡4267ms、选择2282ms、插入1036ms</p><p>快速9ms、堆9ms、希尔12ms、归并14ms</p><p>计数3ms、基数7ms、桶38ms</p><p>Arrays.sort:11ms</p><p>Collections.sort:24ms</p><p>执行10万个随机数的排序，同一台机器相同条件下的测试结果：</p><p>冒泡16406ms、选择8633ms、插入4067ms</p><p>快速16ms、堆16ms、希尔19ms、归并21ms</p><p>计数6ms、基数11ms、桶49ms</p><p>Arrays.sort:19ms</p><p>Collections.sort:47ms</p><p>排序效率排名：计数、基数 、快速、堆、希尔、归并、桶、插入、选择、冒泡</p></li></ol></blockquote><blockquote><ol start="3"><li><p>根据其稳定性，可以分为稳定排序和不稳定排序</p><p>稳定排序：值相同的元素在排序后仍然保持着排序前的顺序</p><p>不稳定排序：值相同的元素在排序后打乱了排序前的顺序。（选择、快速、堆、希尔）</p></li></ol></blockquote></article><div class="post-copyright"><div class="copyright-cc-box"><i class="anzhiyufont anzhiyu-icon-copyright"></i></div><div class="post-copyright__author_box"><a class="post-copyright__author_img" target="_blank" rel="noopener" href="https://insectmk.cn" title="头像"><img class="post-copyright__author_img_back" src="/static/img/head/insectmk.jpg" title="头像" alt="头像"><img class="post-copyright__author_img_front" src="/static/img/head/insectmk.jpg" title="头像" alt="头像"></a><div class="post-copyright__author_name">InsectMk</div><div class="post-copyright__author_desc">今天特别开心！</div></div><div class="post-copyright__post__info"><a class="post-copyright__original" title="该文章为原创文章，注意版权协议" href="https://insectmk.top/posts/1a656c15/">原创</a><a class="post-copyright-title"><span onclick='rm.copyPageUrl("https://insectmk.top/posts/1a656c15/")'>数据的排序</span></a></div><div class="post-tools" id="post-tools"><div class="post-tools-left"><div class="rewardLeftButton"></div><div class="shareRight"><div class="share-link mobile"><div class="share-qrcode"><div class="share-button" title="使用手机访问这篇文章"><i class="anzhiyufont anzhiyu-icon-qrcode"></i></div><div class="share-main"><div class="share-main-all"><div id="qrcode" title="https://insectmk.top/posts/1a656c15/"></div><div class="reward-dec">使用手机访问这篇文章</div></div></div></div></div><div class="share-link weibo"><a class="share-button" target="_blank" href="https://service.weibo.com/share/share.php?title=undefined&amp;url=https://insectmk.top/posts/1a656c15/&amp;pic=undefined" rel="external nofollow noreferrer noopener"><i class="anzhiyufont anzhiyu-icon-weibo"></i></a></div><script>function copyCurrentPageUrl(){var e=window.location.href,t=document.createElement("input");t.setAttribute("value",e),document.body.appendChild(t),t.select(),t.setSelectionRange(0,99999),document.execCommand("copy"),document.body.removeChild(t)}</script><div class="share-link copyurl"><div class="share-button" id="post-share-url" title="复制链接" onclick="copyCurrentPageUrl()"><i class="anzhiyufont anzhiyu-icon-link"></i></div></div></div></div></div><div class="post-copyright__notice"><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://insectmk.top" target="_blank">InsectMk的个人空间</a>！</span></div></div><div class="post-tools-right"><div class="tag_share"><div class="post-meta__box"><div class="post-meta__box__tag-list"><a class="post-meta__box__tags" href="/tags/Java/"><span class="tags-punctuation"><i class="anzhiyufont anzhiyu-icon-tag"></i></span>Java<span class="tagsPageCount">35</span></a><a class="post-meta__box__tags" href="/tags/%E5%8D%83%E9%94%8B%E6%95%99%E8%82%B2/"><span class="tags-punctuation"> <i class="anzhiyufont anzhiyu-icon-tag"></i></span>千锋教育<span class="tagsPageCount">30</span></a><a class="post-meta__box__tags" href="/tags/%E5%9F%B9%E8%AE%AD/"><span class="tags-punctuation"> <i class="anzhiyufont anzhiyu-icon-tag"></i></span>培训<span class="tagsPageCount">30</span></a></div></div></div><div class="post_share"><div class="social-share" data-image="https://image.insectmk.cn/hexo-gitee-blog/cover/github-insectmk.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.cbd.int/butterfly-extsrc@1.1.3/sharejs/dist/css/share.min.css" media="print" onload='this.media="all"'><script src="https://cdn.cbd.int/butterfly-extsrc@1.1.3/sharejs/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/posts/8eef9745/"><img class="prev-cover" src="/" onerror='onerror=null,src="/static/img/website/404.jpg"' alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">数组的查找</div></div></a></div><div class="next-post pull-right"><a href="/posts/340249a9/"><img class="next-cover" src="/" onerror='onerror=null,src="/static/img/website/404.jpg"' alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">数组</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="anzhiyufont anzhiyu-icon-thumbs-up fa-fw" style="font-size:1.5rem;margin-right:4px"></i><span>喜欢这篇文章的人也看了</span></div><div class="relatedPosts-list"><div><a href="/posts/b51f2d85/" title="动&#x2F;静态语言、强&#x2F;弱类型语言、编译型&#x2F;解释形语言的区别"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">动&#x2F;静态语言、强&#x2F;弱类型语言、编译型&#x2F;解释形语言的区别</div></div></a></div><div><a href="/posts/836f8ca6/" title="千锋JavaDay01"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">千锋JavaDay01</div></div></a></div><div><a href="/posts/f9fe4650/" title="主方法的构造"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">主方法的构造</div></div></a></div><div><a href="/posts/1a66dd1c/" title="千锋JavaDay02"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">千锋JavaDay02</div></div></a></div><div><a href="/posts/d88f5f05/" title="字节码文件解析"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">字节码文件解析</div></div></a></div><div><a href="/posts/18c98bc7/" title="深入乱码"><img class="cover" src="/" alt="cover"><div class="content is-center"><div class="date"><i class="anzhiyufont anzhiyu-icon-calendar-days fa-fw"></i> 2023-06-26</div><div class="title">深入乱码</div></div></a></div></div></div><hr><div id="post-comment"><div class="comment-head"><div class="comment-headline"><i class="anzhiyufont anzhiyu-icon-comments"></i><span> 评论</span></div><div class="comment-randomInfo"><a onclick="anzhiyu.addRandomCommentInfo()" href="javascript:void(0)">匿名评论</a><a href="/privacy" style="margin-left:4px">隐私政策</a></div></div><div class="comment-wrap"><div><div id="waline-wrap"></div></div></div></div><div class="comment-barrage"></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="card-content"><div class="author-info-avatar"><img class="avatar-img" src="/static/img/head/insectmk.jpg" onerror='this.onerror=null,this.src="/static/img/website/friend_404.gif"' alt="avatar"></div><div class="author-info__description"><div style="line-height:1.38;margin:.6rem 0;text-align:justify;color:rgba(255,255,255,.8)">这有关于<b style="color:#fff">程序开发、部署</b>相关的问题和看法，还有<b style="color:#fff">软件推荐</b>和<b style="color:#fff">分享</b>。</div><div style="line-height:1.38;margin:.6rem 0;text-align:justify;color:rgba(255,255,255,.8)">相信你可以在这里找到对你有用的<b style="color:#fff">知识</b>和<b style="color:#fff">教程</b>。</div></div><div class="author-info__bottom-group"><a class="author-info__bottom-group-left" href="/"><h1 class="author-info__name">InsectMk</h1><div class="author-info__desc">今天特别开心！</div></a><div class="card-info-social-icons is-center"><a class="social-icon faa-parent animated-hover" href="https://gitee.com/insectmk" target="_blank" title="Gitee"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-gitee"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/static/img/website/contact/qq.png" target="_blank" title="QQ"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-qq"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/static/img/website/contact/wechat.png" target="_blank" title="WeChat"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-wechat"></use></svg></a><a class="social-icon faa-parent animated-hover" href="/atom.xml" target="_blank" title="订阅-ATOM"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-rss"></use></svg></a><a class="social-icon faa-parent animated-hover" href="mailto:3067836615@qq.com" target="_blank" title="Email"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-youxiang-"></use></svg></a></div></div></div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-bars"></i><span>文章目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E7%BB%84%E7%9A%84%E6%8E%92%E5%BA%8F"><span class="toc-number">1.</span> <span class="toc-text">数组的排序</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%89%8D%E8%A8%80"><span class="toc-number">1.1.</span> <span class="toc-text">前言</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8E%92%E5%BA%8F%E6%A6%82%E5%BF%B5"><span class="toc-number">1.1.1.</span> <span class="toc-text">排序概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B8%B8%E8%A7%81%E7%9A%84%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E5%88%86%E7%B1%BB"><span class="toc-number">1.1.2.</span> <span class="toc-text">常见的排序算法分类</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%AE%97%E6%B3%95%E7%A8%B3%E5%AE%9A%E6%80%A7"><span class="toc-number">1.1.3.</span> <span class="toc-text">算法稳定性</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%A6%82%E4%BD%95%E5%88%86%E6%9E%90%E7%AE%97%E6%B3%95"><span class="toc-number">1.1.4.</span> <span class="toc-text">如何分析算法</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%88%86%E6%9E%90%E7%AE%97%E6%B3%95%E7%9A%84%E6%89%A7%E8%A1%8C%E6%95%88%E7%8E%87"><span class="toc-number">1.1.4.1.</span> <span class="toc-text">分析算法的执行效率</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%88%86%E6%9E%90%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E7%A8%B3%E5%AE%9A%E6%80%A7"><span class="toc-number">1.1.4.2.</span> <span class="toc-text">分析排序算法的稳定性</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E5%88%86%E6%9E%90%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E5%86%85%E5%AD%98%E6%8D%9F%E8%80%97"><span class="toc-number">1.1.4.3.</span> <span class="toc-text">分析排序算法的内存损耗</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F"><span class="toc-number">1.2.</span> <span class="toc-text">冒泡排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5"><span class="toc-number">1.2.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86"><span class="toc-number">1.2.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0"><span class="toc-number">1.2.3.</span> <span class="toc-text">代码实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8F%A3%E8%AF%80"><span class="toc-number">1.2.4.</span> <span class="toc-text">口诀</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BC%98%E5%8C%96%E4%BB%A3%E7%A0%81"><span class="toc-number">1.2.5.</span> <span class="toc-text">优化代码</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F"><span class="toc-number">1.3.</span> <span class="toc-text">选择排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-1"><span class="toc-number">1.3.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-1"><span class="toc-number">1.3.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-1"><span class="toc-number">1.3.3.</span> <span class="toc-text">代码实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F%E5%B0%8F%E7%BB%93"><span class="toc-number">1.3.4.</span> <span class="toc-text">选择排序小结</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F"><span class="toc-number">1.4.</span> <span class="toc-text">插入排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-2"><span class="toc-number">1.4.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-2"><span class="toc-number">1.4.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-2"><span class="toc-number">1.4.3.</span> <span class="toc-text">代码实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E5%B0%8F%E7%BB%93"><span class="toc-number">1.4.4.</span> <span class="toc-text">插入排序小结</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F"><span class="toc-number">1.5.</span> <span class="toc-text">快速排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-3"><span class="toc-number">1.5.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-3"><span class="toc-number">1.5.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%AD%A5%E9%AA%A4"><span class="toc-number">1.5.3.</span> <span class="toc-text">步骤</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#A-%E5%8F%8C%E8%BE%B9%E5%BE%AA%E7%8E%AF%E6%B3%95"><span class="toc-number">1.5.3.1.</span> <span class="toc-text">A.双边循环法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-3"><span class="toc-number">1.5.3.2.</span> <span class="toc-text">代码实现</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#B-%E5%8D%95%E8%BE%B9%E5%BE%AA%E7%8E%AF%E6%B3%95"><span class="toc-number">1.5.3.3.</span> <span class="toc-text">B.单边循环法</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-4"><span class="toc-number">1.5.3.4.</span> <span class="toc-text">代码实现</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F"><span class="toc-number">1.6.</span> <span class="toc-text">希尔排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-4"><span class="toc-number">1.6.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-4"><span class="toc-number">1.6.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-5"><span class="toc-number">1.6.3.</span> <span class="toc-text">代码实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F%E4%BC%98%E5%8A%A3"><span class="toc-number">1.6.4.</span> <span class="toc-text">希尔排序优劣</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F%E7%A8%B3%E5%AE%9A%E6%80%A7"><span class="toc-number">1.6.5.</span> <span class="toc-text">希尔排序稳定性</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F"><span class="toc-number">1.7.</span> <span class="toc-text">归并排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-5"><span class="toc-number">1.7.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-5"><span class="toc-number">1.7.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-6"><span class="toc-number">1.7.3.</span> <span class="toc-text">代码实现</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%A1%B6%E6%8E%92%E5%BA%8F"><span class="toc-number">1.8.</span> <span class="toc-text">桶排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-6"><span class="toc-number">1.8.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-6"><span class="toc-number">1.8.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-7"><span class="toc-number">1.8.3.</span> <span class="toc-text">代码实现</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F"><span class="toc-number">1.9.</span> <span class="toc-text">基数排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-7"><span class="toc-number">1.9.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-7"><span class="toc-number">1.9.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-8"><span class="toc-number">1.9.3.</span> <span class="toc-text">代码实现</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%AE%A1%E6%95%B0%E6%8E%92%E5%BA%8F"><span class="toc-number">1.10.</span> <span class="toc-text">计数排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-8"><span class="toc-number">1.10.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-8"><span class="toc-number">1.10.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-9"><span class="toc-number">1.10.3.</span> <span class="toc-text">代码实现</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%A0%86%E6%8E%92%E5%BA%8F"><span class="toc-number">1.11.</span> <span class="toc-text">堆排序</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-9"><span class="toc-number">1.11.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-9"><span class="toc-number">1.11.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0-10"><span class="toc-number">1.11.3.</span> <span class="toc-text">代码实现</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#Arrays-sort"><span class="toc-number">1.12.</span> <span class="toc-text">Arrays.sort()</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A6%82%E5%BF%B5-10"><span class="toc-number">1.12.1.</span> <span class="toc-text">概念</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%8E%9F%E7%90%86-10"><span class="toc-number">1.12.2.</span> <span class="toc-text">原理</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%BA%90%E7%A0%81%E6%88%AA%E5%9B%BE"><span class="toc-number">1.12.3.</span> <span class="toc-text">源码截图</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E4%B8%8E%E5%A4%8D%E6%9D%82%E5%BA%A6%E5%BD%92%E7%B1%BB"><span class="toc-number">1.13.</span> <span class="toc-text">排序算法与复杂度归类</span></a></li></ol></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="anzhiyufont anzhiyu-icon-history"></i><span>最近发布</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/posts/98f3f974/" title="美化你的Github个人主页"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/github-insectmk.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="美化你的Github个人主页"></a><div class="content"><a class="title" href="/posts/98f3f974/" title="美化你的Github个人主页">美化你的Github个人主页</a><time datetime="2024-07-30T02:52:23.000Z" title="发表于 2024-07-30 10:52:23">2024-07-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/10d64ca8/" title="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/hexo-butterfly.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）"></a><div class="content"><a class="title" href="/posts/10d64ca8/" title="我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）">我的Hexo博客多主题同时部署的实现思路（Butterfly+安知鱼）</a><time datetime="2024-07-30T01:30:07.000Z" title="发表于 2024-07-30 09:30:07">2024-07-30</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/129b7f4a/" title="使用Spring AI对接Ollama搭建自己的智能问答网站"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/ollama.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="使用Spring AI对接Ollama搭建自己的智能问答网站"></a><div class="content"><a class="title" href="/posts/129b7f4a/" title="使用Spring AI对接Ollama搭建自己的智能问答网站">使用Spring AI对接Ollama搭建自己的智能问答网站</a><time datetime="2024-07-20T02:45:24.000Z" title="发表于 2024-07-20 10:45:24">2024-07-20</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/9c83ed78/" title="无需更改源码！让你的Hexo的文章在首页隐藏"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/hexo-hide-posts.jpg" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="无需更改源码！让你的Hexo的文章在首页隐藏"></a><div class="content"><a class="title" href="/posts/9c83ed78/" title="无需更改源码！让你的Hexo的文章在首页隐藏">无需更改源码！让你的Hexo的文章在首页隐藏</a><time datetime="2024-07-19T02:22:45.000Z" title="发表于 2024-07-19 10:22:45">2024-07-19</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/posts/9348d5be/" title="使用Cloudflare加速Docker镜像下载"><img src="https://image.insectmk.cn/hexo-gitee-blog/cover/docker.png" onerror='this.onerror=null,this.src="/static/img/website/404.jpg"' alt="使用Cloudflare加速Docker镜像下载"></a><div class="content"><a class="title" href="/posts/9348d5be/" title="使用Cloudflare加速Docker镜像下载">使用Cloudflare加速Docker镜像下载</a><time datetime="2024-06-13T08:01:10.000Z" title="发表于 2024-06-13 16:01:10">2024-06-13</time></div></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div id="workboard"><div id="runtimeTextTip"></div></div><p id="ghbdages"><a class="github-badge" target="_blank" href="https://hexo.io/" style="margin-inline:5px" data-title="博客框架为Hexo_v7.3.0" title="博客框架为Hexo_v7.3.0"><img src="https://npm.elemecdn.com/anzhiyu-blog@2.1.5/img/badge/Frame-Hexo.svg" alt="博客框架为Hexo_v7.3.0"></a><a class="github-badge" target="_blank" href="https://blog.anheyu.com/" style="margin-inline:5px" data-title="本站使用AnZhiYu主题" title="本站使用AnZhiYu主题"><img src="https://npm.elemecdn.com/anzhiyu-theme-static@1.0.9/img/Theme-AnZhiYu-2E67D3.svg" alt="本站使用AnZhiYu主题"></a></p></div><div id="footer-bar"><div class="footer-bar-links"><div class="footer-bar-left"><div id="footer-bar-tips"><div class="copyright">&copy;2020 - 2024 By <a class="footer-bar-link" href="/" title="InsectMk" target="_blank">InsectMk</a></div></div><div id="footer-type-tips"></div></div><div class="footer-bar-right"><a class="footer-bar-link" target="_blank" rel="noopener" href="https://github.com/anzhiyu-c/hexo-theme-anzhiyu" title="主题">主题</a><a class="footer-bar-link" target="_blank" rel="noopener" href="https://beian.miit.gov.cn/" title="蜀ICP备2023013851号-2">蜀ICP备2023013851号-2</a><a class="footer-bar-link" target="_blank" rel="noopener" href="https://beian.mps.gov.cn/#/query/webSearch?code=51142202000154" title="川公网安备51142202000154号">川公网安备51142202000154号</a></div></div></div></footer></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="sidebar-site-data site-data is-center"><a href="/archives/" title="archive"><div class="headline">文章</div><div class="length-num">121</div></a><a href="/tags/" title="tag"><div class="headline">标签</div><div class="length-num">117</div></a><a href="/categories/" title="category"><div class="headline">分类</div><div class="length-num">14</div></a></div><span class="sidebar-menu-item-title">功能</span><div class="sidebar-menu-item"><a class="darkmode_switchbutton menu-child" href="javascript:void(0);" title="显示模式"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i><span>显示模式</span></a></div><div class="back-menu-list-groups"><div class="back-menu-list-group"><div class="back-menu-list-title">网页</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://insectmk.cn/" title="主博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="主博客"><span class="back-menu-item-text">主博客</span></a><a class="back-menu-item" href="https://insectmk.top/" title="次博客"><img class="back-menu-item-icon" src="/static/img/website/favicon.jpg" alt="次博客"><span class="back-menu-item-text">次博客</span></a></div></div><div class="back-menu-list-group"><div class="back-menu-list-title">项目</div><div class="back-menu-list"><a class="back-menu-item" target="_blank" rel="noopener" href="https://gitee.com/insectmk/chatbot-web" title="智能聊天机器人网站"><img class="back-menu-item-icon" src="https://image.insectmk.cn/hexo-gitee-blog/project/icon/chatbot-web.jpg" alt="智能聊天机器人网站"><span class="back-menu-item-text">智能聊天机器人网站</span></a></div></div></div><div class="menus_items"><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-home"></use></svg><span>主页</span></a></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-hand-peace"></use></svg><span>娱乐</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/entertainment/gallery/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-images"></use></svg><span>图库</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-comments"></use></svg><span>交流</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/contact/comments/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-paper-plane"></use></svg><span>留言板</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/contact/link/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-link"></use></svg><span>友链</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-compass"></use></svg><span>目录</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/categories/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-archive"></use></svg><span>分类</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/tags/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-tags"></use></svg><span>标签</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/archives/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-folder-open"></use></svg><span>归档</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-server"></use></svg><span>服务</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/server/left4dead2/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-icons-left__dead_"></use></svg><span>求生之路</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/server/minecraft/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-minecraft"></use></svg><span>我的世界</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-clipboard"></use></svg><span>日志</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/log/website/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-website-with-different-sections"></use></svg><span>个人网站</span></a></li><li><a class="site-page child faa-parent animated-hover" href="/log/pc/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-desktop"></use></svg><span>个人电脑</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="javascript:void(0);"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-bars"></use></svg><span>其他</span></a><ul class="menus_item_child"><li><a class="site-page child faa-parent animated-hover" href="/extend/remind/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-note"></use></svg><span>备忘</span></a></li></ul></div><div class="menus_item"><a class="site-page faa-parent animated-hover" href="/about/"><svg class="icon faa-tada" aria-hidden="true"><use xlink:href="#icon-id-card"></use></svg><span>关于</span></a></div></div><span class="sidebar-menu-item-title">标签</span><div class="card-tags"><div class="item-headline"></div><div class="card-tag-cloud"><a href="/tags/AOP/" style="font-size:.88rem">AOP<sup>1</sup></a><a href="/tags/Butterfly/" style="font-size:.88rem">Butterfly<sup>4</sup></a><a href="/tags/Docker/" style="font-size:.88rem">Docker<sup>6</sup></a><a href="/tags/ElementUI/" style="font-size:.88rem">ElementUI<sup>1</sup></a><a href="/tags/Frp/" style="font-size:.88rem">Frp<sup>1</sup></a><a href="/tags/Hexo/" style="font-size:.88rem;font-weight:500;color:var(--anzhiyu-lighttext)">Hexo<sup>8</sup></a><a href="/tags/IntelliJ-IDEA/" style="font-size:.88rem">IntelliJ IDEA<sup>1</sup></a><a href="/tags/JDK/" style="font-size:.88rem">JDK<sup>1</sup></a><a href="/tags/JWT/" style="font-size:.88rem">JWT<sup>1</sup></a><a href="/tags/Java/" style="font-size:.88rem">Java<sup>35</sup></a><a href="/tags/Junit/" style="font-size:.88rem">Junit<sup>1</sup></a><a href="/tags/Leanote/" style="font-size:.88rem">Leanote<sup>1</sup></a><a href="/tags/Maven/" style="font-size:.88rem">Maven<sup>2</sup></a><a href="/tags/MyBatisPlus/" style="font-size:.88rem">MyBatisPlus<sup>1</sup></a><a href="/tags/MySQL5-7/" style="font-size:.88rem">MySQL5.7<sup>1</sup></a><a href="/tags/Mybatis/" style="font-size:.88rem">Mybatis<sup>1</sup></a><a href="/tags/MybatisPlus/" style="font-size:.88rem">MybatisPlus<sup>1</sup></a><a href="/tags/OSS/" style="font-size:.88rem">OSS<sup>1</sup></a><a href="/tags/Spring/" style="font-size:.88rem">Spring<sup>2</sup></a><a href="/tags/Spring-Boot/" style="font-size:.88rem">SpringBoot<sup>6</sup></a><a href="/tags/Vue2/" style="font-size:.88rem">Vue2<sup>9</sup></a><a href="/tags/Vue3/" style="font-size:.88rem">Vue3<sup>1</sup></a><a href="/tags/Vuetify/" style="font-size:.88rem">Vuetify<sup>1</sup></a><a href="/tags/Vuex/" style="font-size:.88rem">Vuex<sup>1</sup></a><a href="/tags/Waline/" style="font-size:.88rem">Waline<sup>3</sup></a><a href="/tags/mvc/" style="font-size:.88rem">mvc<sup>3</sup></a><a href="/tags/mybatis/" style="font-size:.88rem">mybatis<sup>1</sup></a><a href="/tags/profile/" style="font-size:.88rem">profile<sup>1</sup></a><a href="/tags/spring/" style="font-size:.88rem">spring<sup>5</sup></a><a href="/tags/springboot/" style="font-size:.88rem">springboot<sup>4</sup></a><a href="/tags/transaction/" style="font-size:.88rem">transaction<sup>1</sup></a><a href="/tags/yaml/" style="font-size:.88rem">yaml<sup>2</sup></a><a href="/tags/%E4%B8%AA%E4%BA%BA%E5%8D%9A%E5%AE%A2/" style="font-size:.88rem">个人博客<sup>11</sup></a><a href="/tags/%E4%BA%8B%E5%8A%A1/" style="font-size:.88rem">事务<sup>1</sup></a><a href="/tags/%E5%88%86%E9%A1%B5/" style="font-size:.88rem">分页<sup>1</sup></a><a href="/tags/%E5%89%8D%E7%AB%AF/" style="font-size:.88rem;font-weight:500;color:var(--anzhiyu-lighttext)">前端<sup>1</sup></a><a href="/tags/%E6%9C%8D%E5%8A%A1%E5%99%A8/" style="font-size:.88rem">服务器<sup>20</sup></a><a href="/tags/%E6%AF%95%E4%B8%9A%E8%AE%BE%E8%AE%A1/" style="font-size:.88rem">毕业设计<sup>14</sup></a><a href="/tags/%E7%A6%85%E9%81%93/" style="font-size:.88rem">禅道<sup>1</sup></a><a href="/tags/%E7%BB%BF%E8%89%B2%E8%A7%A3%E5%8E%8B/" style="font-size:.88rem">绿色解压<sup>1</sup></a></div></div><hr></div></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="anzhiyufont anzhiyu-icon-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="anzhiyufont anzhiyu-icon-arrows-left-right"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="设置"><i class="anzhiyufont anzhiyu-icon-gear"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="anzhiyufont anzhiyu-icon-list-ul"></i></button><button id="chat-btn" type="button" title="聊天"><i class="anzhiyufont anzhiyu-icon-comment-sms"></i></button><a id="to_comment" href="#post-comment" title="直达评论"><i class="anzhiyufont anzhiyu-icon-comments"></i></a><button id="go-up" type="button" title="回到顶部"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i></button></div></div><div id="nav-music"><a id="nav-music-hoverTips" onclick="anzhiyu.musicToggle()" accesskey="m">播放音乐</a><div id="console-music-bg"></div><meting-js id="975968032" server="netease" type="playlist" mutex="true" preload="none" theme="var(--anzhiyu-main)" data-lrctype="0" order="random" volume="0.7"></meting-js></div><div id="local-search"><div class="search-dialog"><nav class="search-nav"><span class="search-dialog-title">搜索</span><span id="loading-status"></span><button class="search-close-button"><i class="anzhiyufont anzhiyu-icon-xmark"></i></button></nav><div class="is-center" id="loading-database"><i class="anzhiyufont anzhiyu-icon-spinner anzhiyu-pulse-icon"></i><span> 数据库加载中</span></div><div class="search-wrap"><div id="local-search-input"><div class="local-search-box"><input class="local-search-box--input" placeholder="搜索文章" type="text"></div></div><hr><div id="local-search-results"></div></div></div><div id="search-mask"></div></div><div id="rightMenu"><div class="rightMenu-group rightMenu-small"><div class="rightMenu-item" id="menu-backward"><i class="anzhiyufont anzhiyu-icon-arrow-left"></i></div><div class="rightMenu-item" id="menu-forward"><i class="anzhiyufont anzhiyu-icon-arrow-right"></i></div><div class="rightMenu-item" id="menu-refresh"><i class="anzhiyufont anzhiyu-icon-arrow-rotate-right" style="font-size:1rem"></i></div><div class="rightMenu-item" id="menu-top"><i class="anzhiyufont anzhiyu-icon-arrow-up"></i></div></div><div class="rightMenu-group rightMenu-line rightMenuPlugin"><div class="rightMenu-item" id="menu-copytext"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制选中文本</span></div><div class="rightMenu-item" id="menu-pastetext"><i class="anzhiyufont anzhiyu-icon-paste"></i><span>粘贴文本</span></div><a class="rightMenu-item" id="menu-commenttext"><i class="anzhiyufont anzhiyu-icon-comment-medical"></i><span>引用到评论</span></a><div class="rightMenu-item" id="menu-newwindow"><i class="anzhiyufont anzhiyu-icon-window-restore"></i><span>新窗口打开</span></div><div class="rightMenu-item" id="menu-copylink"><i class="anzhiyufont anzhiyu-icon-link"></i><span>复制链接地址</span></div><div class="rightMenu-item" id="menu-copyimg"><i class="anzhiyufont anzhiyu-icon-images"></i><span>复制此图片</span></div><div class="rightMenu-item" id="menu-downloadimg"><i class="anzhiyufont anzhiyu-icon-download"></i><span>下载此图片</span></div><div class="rightMenu-item" id="menu-newwindowimg"><i class="anzhiyufont anzhiyu-icon-window-restore"></i><span>新窗口打开图片</span></div><div class="rightMenu-item" id="menu-search"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span>站内搜索</span></div><div class="rightMenu-item" id="menu-searchBaidu"><i class="anzhiyufont anzhiyu-icon-magnifying-glass"></i><span>百度搜索</span></div><div class="rightMenu-item" id="menu-music-toggle"><i class="anzhiyufont anzhiyu-icon-play"></i><span>播放音乐</span></div><div class="rightMenu-item" id="menu-music-back"><i class="anzhiyufont anzhiyu-icon-backward"></i><span>切换到上一首</span></div><div class="rightMenu-item" id="menu-music-forward"><i class="anzhiyufont anzhiyu-icon-forward"></i><span>切换到下一首</span></div><div class="rightMenu-item" id="menu-music-playlist" onclick="window.open(&quot;https://y.qq.com/n/ryqq/playlist/8802438608&quot;, &quot;_blank&quot;);" style="display:none"><i class="anzhiyufont anzhiyu-icon-radio"></i><span>查看所有歌曲</span></div><div class="rightMenu-item" id="menu-music-copyMusicName"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制歌名</span></div></div><div class="rightMenu-group rightMenu-line rightMenuOther"><a class="rightMenu-item menu-link" id="menu-randomPost"><i class="anzhiyufont anzhiyu-icon-shuffle"></i><span>随便逛逛</span></a><a class="rightMenu-item menu-link" href="/categories/"><i class="anzhiyufont anzhiyu-icon-cube"></i><span>博客分类</span></a><a class="rightMenu-item menu-link" href="/tags/"><i class="anzhiyufont anzhiyu-icon-tags"></i><span>文章标签</span></a></div><div class="rightMenu-group rightMenu-line rightMenuOther"><a class="rightMenu-item" id="menu-copy" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-copy"></i><span>复制地址</span></a><a class="rightMenu-item" id="menu-commentBarrage" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-message"></i><span class="menu-commentBarrage-text">关闭热评</span></a><a class="rightMenu-item" id="menu-darkmode" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-circle-half-stroke"></i><span class="menu-darkmode-text">深色模式</span></a><a class="rightMenu-item" id="menu-translate" href="javascript:void(0);"><i class="anzhiyufont anzhiyu-icon-language"></i><span>轉為繁體</span></a></div></div><div id="rightmenu-mask"></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.cbd.int/@fancyapps/ui@5.0.28/dist/fancybox/fancybox.umd.js"></script><script src="https://cdn.cbd.int/instant.page@5.2.0/instantpage.js" type="module"></script><script src="https://cdn.cbd.int/node-snackbar@0.1.16/dist/snackbar.min.js"></script><canvas id="universe"></canvas><script async src="https://npm.elemecdn.com/anzhiyu-theme-static@1.0.0/dark/dark.js"></script><script>var HoldLog=console.log;console.log=function(){};let now1=new Date;queueMicrotask(()=>{function o(){HoldLog.apply(console,arguments)}var c=new Date("04/11/2022 14:03:44"),c=(now1.setTime(now1.getTime()+250),(now1-c)/1e3/60/60/24),c=["欢迎使用安知鱼!","生活明朗, 万物可爱",`
        
       █████╗ ███╗   ██╗███████╗██╗  ██╗██╗██╗   ██╗██╗   ██╗
      ██╔══██╗████╗  ██║╚══███╔╝██║  ██║██║╚██╗ ██╔╝██║   ██║
      ███████║██╔██╗ ██║  ███╔╝ ███████║██║ ╚████╔╝ ██║   ██║
      ██╔══██║██║╚██╗██║ ███╔╝  ██╔══██║██║  ╚██╔╝  ██║   ██║
      ██║  ██║██║ ╚████║███████╗██║  ██║██║   ██║   ╚██████╔╝
      ╚═╝  ╚═╝╚═╝  ╚═══╝╚══════╝╚═╝  ╚═╝╚═╝   ╚═╝    ╚═════╝
        
        `,"已上线",Math.floor(c),"天","©2020 By 安知鱼 V1.6.12"],e=["NCC2-036","调用前置摄像头拍照成功，识别为【小笨蛋】.","Photo captured: ","🤪"];setTimeout(o.bind(console,`
%c${c[0]} %c ${c[1]} %c ${c[2]} %c${c[3]}%c ${c[4]}%c ${c[5]}

%c ${c[6]}
`,"color:#425AEF","","color:#425AEF","color:#425AEF","","color:#425AEF","")),setTimeout(o.bind(console,`%c ${e[0]} %c ${e[1]} %c 
${e[2]} %c
${e[3]}
`,"color:white; background-color:#4fd953","","",'background:url("https://npm.elemecdn.com/anzhiyu-blog@1.1.6/img/post/common/tinggge.gif") no-repeat;font-size:450%')),setTimeout(o.bind(console,"%c WELCOME %c 你好，小笨蛋.","color:white; background-color:#4f90d9","")),setTimeout(console.warn.bind(console,"%c ⚡ Powered by 安知鱼 %c 你正在访问 InsectMk 的博客.","color:white; background-color:#f0ad4e","")),setTimeout(o.bind(console,"%c W23-12 %c 你已打开控制台.","color:white; background-color:#4f90d9","")),setTimeout(console.warn.bind(console,"%c S013-782 %c 你现在正处于监控中.","color:white; background-color:#d9534f",""))})</script><script async src="/anzhiyu/random.js"></script><script async>!function(){var n,r,o,a,i,e=new Date("04/11/2022 14:03:44"),l=new Date;setInterval(()=>{var t;if(l=new Date,i=l.getHours(),t=(l-e)/1e3/60/60/24,n=Math.floor(t),t=(l-e)/1e3/60/60-24*n,r=Math.floor(t),1==String(r).length&&(r="0"+r),t=(l-e)/1e3/60-1440*n-60*r,o=Math.floor(t),1==String(o).length&&(o="0"+o),t=(l-e)/1e3-86400*n-3600*r-60*o,a=Math.round(t),1==String(a).length&&(a="0"+a),document.getElementById("footer")){let e="";e=(i<18&&9<=i||null!=(t=document.querySelector("#workboard .workSituationImg"))&&(t.src="",t.title="",t.alt=""),`本站居然运行了 ${n} 天<span id='runtime'> ${r} 小时 ${o} 分 ${a} 秒 </span><i class='anzhiyufont anzhiyu-icon-heartbeat' style='color:red'></i>`),document.getElementById("runtimeTextTip")&&(document.getElementById("runtimeTextTip").innerHTML=e)}},1e3)}()</script><script src="/js/search/local-search.js"></script><div class="js-pjax"><script>(()=>{let e=()=>{Waline.init(Object.assign({el:"#waline-wrap",serverURL:"https://waline-server.insectmk.cn/",pageview:!0,dark:'html[data-theme="dark"]',path:window.location.pathname,comment:!0},{reaction:["/static/img/waline/tieba_agree.png","/static/img/waline/tieba_look_down.png","/static/img/waline/tieba_sunglasses.png","/static/img/waline/tieba_pick_nose.png","/static/img/waline/tieba_awkward.png","/static/img/waline/tieba_sleep.png"],requiredMeta:["nick","mail"],locale:{placeholder:"欢迎评论哟~"}}))};var i=async()=>{"object"==typeof Waline||(await getCSS("https://cdn.cbd.int/@waline/client@2.15.5/dist/waline.css"),await getScript("https://cdn.cbd.int/@waline/client@2.15.5/dist/waline.js")),e()};setTimeout(i,0)})()</script><input type="hidden" name="page-type" id="page-type" value="post"></div><script>window.addEventListener("load",()=>{let t=e=>e=""!==e&&150<(e=(e=(e=(e=e.replace(/<img.*?src="(.*?)"?[^\>]+>/gi,"[图片]")).replace(/<a[^>]+?href=["']?([^"']+)["']?[^>]*>([^<]+)<\/a>/gi,"[链接]")).replace(/<pre><code>.*?<\/pre>/gi,"[代码]")).replace(/<[^>]+>/g,"")).length?e.substring(0,150)+"...":e,a=t=>{let a="";if(t.length)for(let e=0;e<t.length;e++)a=(a=(a+="<div class='aside-list-item'>")+`<a href='${t[e].url}' class='thumbnail'><img src='${t[e].avatar}' alt='${t[e].nick}'></a>`)+`<div class='content'>
        <a class='comment' href='${t[e].url}' title='${t[e].content}'>${t[e].content}</a>
        <div class='name'><span>${t[e].nick} / </span><time datetime="${t[e].date}">${anzhiyu.diffDate(t[e].date,!0)}</time></div>
        </div></div>`;else a+="没有评论";var e=document.querySelector("#card-newest-comments .aside-list");e&&(e.innerHTML=a),window.lazyLoadInstance&&window.lazyLoadInstance.update(),window.pjax&&window.pjax.refresh(e)};var e=()=>{var e;document.querySelector("#card-newest-comments .aside-list")&&((e=saveToLocal.get("waline-newest-comments"))?a(JSON.parse(e)):(async()=>{try{var e=(await(await fetch("https://waline-server.insectmk.cn/api/comment?type=recent&count=6",{method:"GET"})).json()).data.map(e=>({content:t(e.comment),avatar:e.avatar,nick:e.nick,url:e.url+"#"+e.objectId,date:e.time||e.insertedAt}));saveToLocal.set("waline-newest-comments",JSON.stringify(e),10/1440),a(e)}catch(e){console.error(e),document.querySelector("#card-newest-comments .aside-list").textContent="无法获取评论，请确认相关配置是否正确"}})())};e(),document.addEventListener("pjax:complete",e)})</script><script>var visitorMail=""</script><script async data-pjax src="https://cdn.cbd.int/anzhiyu-theme-static@1.0.0/waterfall/waterfall.js"></script><script src="https://lf3-cdn-tos.bytecdntp.com/cdn/expire-1-M/qrcodejs/1.0.0/qrcode.min.js"></script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.1.9/icon/ali_iconfont_css.css"><script async src="//at.alicdn.com/t/c/font_3795172_6hp27xdg2x7.js"></script><script>(()=>{var a,t,h,e;window.ChatraSetup={startHidden:!0},window.chatBtnFn=()=>{document.getElementById("chatra").classList.contains("chatra--expanded")?(Chatra("minimizeWidget"),Chatra("hide")):(Chatra("openChat",!0),Chatra("show"))};a=document,t=window,h="Chatra",t.ChatraID="SjkKhfiLMpdfaPPhc",e=a.createElement("script"),t[h]=t[h]||function(){(t[h].q=t[h].q||[]).push(arguments)},e.async=!0,e.src="https://call.chatra.io/chatra.js",a.head&&a.head.appendChild(e)})()</script><link rel="stylesheet" href="https://cdn.cbd.int/anzhiyu-theme-static@1.0.0/aplayer/APlayer.min.css" media="print" onload='this.media="all"'><script src="https://cdn.cbd.int/anzhiyu-blog-static@1.0.1/js/APlayer.min.js"></script><script src="https://cdn.cbd.int/hexo-anzhiyu-music@1.0.1/assets/js/Meting2.min.js"></script><script src="https://cdn.cbd.int/pjax@0.2.8/pjax.min.js"></script><script>let pjaxSelectors=["head > title","#config-diff","#body-wrap","#rightside-config-hide","#rightside-config-show",".js-pjax"];var pjax=new Pjax({elements:'a:not([target="_blank"])',selectors:pjaxSelectors,cacheBust:!1,analytics:!1,scrollRestoration:!1});document.addEventListener("pjax:send",function(){if(anzhiyu.removeGlobalFnEvent("pjax"),anzhiyu.removeGlobalFnEvent("themeChange"),document.getElementById("rightside").classList.remove("rightside-show"),window.aplayers)for(let e=0;e<window.aplayers.length;e++)window.aplayers[e].options.fixed||window.aplayers[e].destroy();"object"==typeof typed&&typed.destroy();var e=document.body.classList;e.contains("read-mode")&&e.remove("read-mode")}),document.addEventListener("pjax:complete",function(){window.refreshFn(),document.querySelectorAll("script[data-pjax]").forEach(e=>{let t=document.createElement("script");var a=e.text||e.textContent||e.innerHTML||"";Array.from(e.attributes).forEach(e=>t.setAttribute(e.name,e.value)),t.appendChild(document.createTextNode(a)),e.parentNode.replaceChild(t,e)}),GLOBAL_CONFIG.islazyload&&window.lazyLoadInstance.update(),"function"==typeof panguInit&&panguInit(),"function"==typeof gtag&&gtag("config","",{page_path:window.location.pathname}),"object"==typeof _hmt&&_hmt.push(["_trackPageview",window.location.pathname]),"function"==typeof loadMeting&&document.getElementsByClassName("aplayer").length&&loadMeting(),"object"==typeof Prism&&Prism.highlightAll()}),document.addEventListener("pjax:error",e=>{404===e.request.status&&pjax.loadUrl("/404")})</script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><script charset="UTF-8" src="https://cdn.cbd.int/anzhiyu-theme-static@1.1.5/accesskey/accesskey.js"></script></div><div id="popup-window"><div class="popup-window-title">通知</div><div class="popup-window-divider"></div><div class="popup-window-content"><div class="popup-tip">你好呀</div><div class="popup-link"><i class="anzhiyufont anzhiyu-icon-arrow-circle-right"></i></div></div></div></body></html>